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

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

---

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

---

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
Content:
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
The Duals of Upward Planar Graphs on Cylinders....Pages 91-102
The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases....Pages 103-113
Determining the L(2,1)-Span in Polynomial Space....Pages 114-125
On the Minimum Degree Up to Local Complementation: Bounds and Complexity....Pages 126-137
On the Stable Degree of Graphs....Pages 138-147
A 9k Kernel for Nonseparating Independent Set in Planar Graphs....Pages 148-159
Bisections above Tight Lower Bounds....Pages 160-171
On Group Feedback Vertex Set Parameterized by the Size of the Cutset....Pages 172-183
Fault Tolerant Additive Spanners....Pages 184-193
Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications....Pages 194-205
Approximating Infeasible 2VPI-Systems....Pages 206-214
Hydras: Directed Hypergraphs and Horn Formulas....Pages 215-224
Minimum Weight Dynamo and Fast Opinion Spreading....Pages 225-236
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill....Pages 237-248
On the Recognition of k-Equistable Graphs....Pages 249-261
Maximum Induced Multicliques and Complete Multipartite Subgraphs in Polygon-Circle Graphs and Circle Graphs....Pages 262-273
Parameterized Domination in Circle Graphs....Pages 274-285
How to Eliminate a Graph....Pages 286-296
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties....Pages 297-307
Back Matter....Pages 308-319
....Pages 320-331