Graph-Theoretic Concepts in Computer Science: 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers

✍ Scribed by Ernst W. Mayr (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2016
• Tongue: English
• Leaves: 516
• Series: Lecture Notes in Computer Science 9224
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes revised selected papers from the 41^st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015, held in Garching, Germany, in June 2015.
The 32 papers presented in this volume were carefully reviewed and selected from 79 submissions. They were organized in topical sections named: invited talks; computational complexity; design and analysis; computational geometry; structural graph theory; graph drawing; and fixed parameter tractability.

✦ Table of Contents

Front Matter....Pages I-XIV
Front Matter....Pages 1-1
Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics....Pages 3-15
Open Problems on Graph Coloring for Special Graph Classes....Pages 16-30
On the Complexity of Approximation and Online Scheduling Problems with Applications to Optical Networks....Pages 31-46
Front Matter....Pages 47-47
The Stable Fixtures Problem with Payments....Pages 49-63
Complexity of Secure Sets....Pages 64-77
On the Tree Search Problem with Non-uniform Costs....Pages 78-89
On the Number of Minimal Separators in Graphs....Pages 90-102
Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks....Pages 103-115
A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs....Pages 116-121
Finding Paths in Grids with Forbidden Transitions....Pages 122-137
The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results....Pages 138-153
Front Matter....Pages 154-168
Minimum Eccentricity Shortest Paths in Some Structured Graph Classes....Pages 169-185
Approximating Source Location and Star Survivable Network Problems....Pages 187-187
On the Complexity of Computing the k-restricted Edge-connectivity of a Graph....Pages 189-202
Front Matter....Pages 203-218
Weak Unit Disk and Interval Representation of Graphs....Pages 219-233
Simultaneous Visibility Representations of Plane st-graphs Using L-shapes....Pages 235-235
An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes....Pages 237-251
Unsplittable Coverings in the Plane....Pages 252-265
Front Matter....Pages 266-280
Induced Minor Free Graphs: Isomorphism and Clique-width....Pages 281-296
On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs....Pages 297-297
Colouring and Covering Nowhere Dense Graphs....Pages 299-311
Parity Linkage and the Erdős-Pósa Property of Odd Cycles Through Prescribed Vertices in Highly Connected Graphs....Pages 312-324
Well-quasi-ordering Does Not Imply Bounded Clique-width....Pages 325-338
A Slice Theoretic Approach for Embedding Problems on Digraphs....Pages 339-350
Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs....Pages 351-359
Front Matter....Pages 360-372
Saturated Simple and 2-simple Topological Graphs with Few Edges....Pages 373-387
Testing Full Outer-2-planarity in Linear Time....Pages 389-389
Front Matter....Pages 391-405
Triangulating Planar Graphs While Keeping the Pathwidth Small....Pages 406-421
Polynomial Kernelization for Removing Induced Claws and Diamonds....Pages 423-423
Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs....Pages 425-439
On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT....Pages 440-455
Recognizing k-equistable Graphs in FPT Time....Pages 456-471
Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques....Pages 472-486
Back Matter....Pages 487-498
....Pages 499-512

✦ Subjects

Discrete Mathematics in Computer Science;Algorithm Analysis and Problem Complexity;Data Structures;Computer Graphics;Geometry;Algorithms