Graph-Theoretic Concepts in Computer Science
Subtitle: 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers
By: edited by Martin Charles Golumbic, Michal Stern, Avivit Levy, Gila Morgenstern
Contributors: Stern, Michal; Levy, Avivit; Morgenstern, Gila; SpringerLink (Online service)
Series: Lecture Notes in Computer Science -- 7551
Publisher: Springer Berlin Heidelberg; Imprint: Springer
Published: 2012
Place of publication: Berlin, Heidelberg
Language: eng
Format: [electronic resource] :
Number of pages: 346
ISBN-13: 9783642346118
Subjects: Computational complexity; Discrete Mathematics in Computer Science; Geometry; Data structures (Computer science); Algorithm Analysis and Problem Complexity; Data Structures; Algorithms; Artificial Intelligence (incl. Robotics); Computer software; Artificial intelligence; Computer science
Description: This book constitutes the thoroughly refereed proceedings of the 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012) held in Jerusalem, Israel on June 26-28, 2012. The 29 revised full papers presented were carefully selected and reviewed from 78 submissions. The papers are solicited describing original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, randomized, parameterized, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, random graphs, diagram methods, and support of these concepts by suitable implementations. The scope of WG includes all applications of graph-theoretic concepts in Computer Science, including data structures, data bases, programming languages, computational geometry, tools for software construction, communications, computing on the web, models of the web and scale-free networks, mobile computing, concurrency, computer architectures, VLSI, artificial intelligence, graphics, CAD, operations research, and pattern recognition
Table of contents: title: <p>Account on Intervals; title: Constructing Resilient Structures in Graphs: Rigid vs. Competitive Fault-Tolerance; title: Alternating Reachabillity and Integer Sum of Closed Alternating Trails: The 3rd Annual Uri N. Peled Memorial Lecture; title: Triangulation and Clique Separator Decomposition of Claw-Free Graphs; title: Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs; title: Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs; title: <i>h</i>-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area; title: The Duals of Upward Planar Graphs on Cylinders; title: On the Minimum Degree Up to Local Complementation: Bounds and Complexity; title: Bisections above Tight Lower Bounds; title: Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications; title: Hydras: Directed Hypergraphs and Horn Formulas; title: Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill; title: Maximum Induced Multicliques and Complete Multipartite Subgraphs in Polygon-Circle Graphs and Circle Graphs; title: Parameterized Domination in Circle Graphs; title: On the Parameterized Complexity of Finding Separators with Non-hereditary Properties.</p>.