Graph-Theoretic Concepts in Computer Science: 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers

✍ Scribed by Dieter Rautenbach (auth.), Martin Charles Golumbic, Michal Stern, Avivit Levy, Gila Morgenstern (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2012
• Tongue: English
• Leaves: 356
• Series: Lecture Notes in Computer Science 7551
• Edition: 1
• Category: Library

✦ Synopsis

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

Front Matter....Pages -
Account on Intervals....Pages 1-1
Constructing Resilient Structures in Graphs: Rigid vs. Competitive Fault-Tolerance....Pages 2-2
Alternating Reachability and Integer Sum of Closed Alternating Trails....Pages 3-3
Student Poster Session....Pages 4-6
Triangulation and Clique Separator Decomposition of Claw-Free Graphs....Pages 7-21
Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs....Pages 22-33
Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs....Pages 34-45
Optimization Problems in Dotted Interval Graphs....Pages 46-56
The Maximum Clique Problem in Multiple Interval Graphs (Extended Abstract)....Pages 57-68
Solutions for the Stable Roommates Problem with Payments....Pages 69-80
Which Multi-peg Tower of Hanoi Problems Are Exponential?....Pages 81-90
h -Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area....Pages 91-102
The Duals of Upward Planar Graphs on Cylinders....Pages 103-113
The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases....Pages 114-125
Determining the L (2,1)-Span in Polynomial Space....Pages 126-137
On the Minimum Degree Up to Local Complementation: Bounds and Complexity....Pages 138-147
On the Stable Degree of Graphs....Pages 148-159
A 9 k Kernel for Nonseparating Independent Set in Planar Graphs....Pages 160-171
Parameterized Algorithms for Even Cycle Transversal ....Pages 172-183
Bisections above Tight Lower Bounds....Pages 184-193
On Group Feedback Vertex Set Parameterized by the Size of the Cutset....Pages 194-205
Fault Tolerant Additive Spanners....Pages 206-214
Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications....Pages 215-224
Approximating Infeasible 2VPI-Systems....Pages 225-236
Hydras: Directed Hypergraphs and Horn Formulas....Pages 237-248
Minimum Weight Dynamo and Fast Opinion Spreading....Pages 249-261
Immediate versus Eventual Conversion: Comparing Geodetic and Hull Numbers in P 3 -Convexity....Pages 262-273
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill....Pages 274-285
On the Recognition of k -Equistable Graphs....Pages 286-296
Maximum Induced Multicliques and Complete Multipartite Subgraphs in Polygon-Circle Graphs and Circle Graphs....Pages 297-307
Parameterized Domination in Circle Graphs....Pages 308-319
How to Eliminate a Graph....Pages 320-331
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties....Pages 332-343
Back Matter....Pages -

✦ Subjects

Discrete Mathematics in Computer Science; Artificial Intelligence (incl. Robotics); Algorithm Analysis and Problem Complexity; Data Structures; Geometry; Algorithms