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

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