Graph-Theoretic Concepts in Computer Science: 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers

✍ Scribed by Dieter Kratsch, Ioan Todinca (eds.)

• Publisher: Springer International Publishing
• Year: 2014
• Tongue: English
• Leaves: 432
• Series: Lecture Notes in Computer Science 8747
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post-conference proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, held in Nouan-le-Fuzelier, France, in June 2014.

The 32 revised full papers presented were carefully reviewed and selected from 80 submissions. The book also includes two invited papers. The papers cover a wide range of topics in graph theory related to computer science, such as design and analysis of sequential, parallel, randomized, parameterized and distributed graph and network algorithms; structural graph theory with algorithmic or complexity applications; computational complexity of graph and network problems; graph grammars, graph rewriting systems and graph modeling; graph drawing and layouts; computational geometry; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications.

✦ Table of Contents

Front Matter....Pages I-XI
Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)....Pages 1-14
Distributedly Testing Cycle-Freeness....Pages 15-28
DMVP: Foremost Waypoint Coverage of Time-Varying Graphs....Pages 29-41
Linear Rank-Width of Distance-Hereditary Graphs....Pages 42-55
Vertex Contact Graphs of Paths on a Grid....Pages 56-68
Deciding the Bell Number for Hereditary Graph Properties....Pages 69-80
Boxicity and Separation Dimension....Pages 81-92
Maximal Induced Matchings in Triangle-Free Graphs....Pages 93-104
Independent Set Reconfiguration in Cographs....Pages 105-116
Structural Parameterizations for Boxicity....Pages 117-128
A New Characterization of $$P_k$$ -free Graphs....Pages 129-138
Contact Representations of Planar Graphs: Extending a Partial Representation is Hard....Pages 139-151
The Maximum Labeled Path Problem....Pages 152-163
Minimum Spanning Tree Verification Under Uncertainty....Pages 164-175
Towards the Hanani-Tutte Theorem for Clustered Graphs....Pages 176-188
On Set Expansion Problems and the Small Set Expansion Conjecture....Pages 189-200
Hadwiger Number of Graphs with Small Chordality....Pages 201-213
Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time....Pages 214-224
Induced Disjoint Paths in Circular-Arc Graphs in Linear Time....Pages 225-237
Near-Linear Time Constant-Factor Approximation Algorithm for Branch-Decomposition of Planar Graphs....Pages 238-249
Parameterized Directed $$k$$ -Chinese Postman Problem and $$k$$ Arc-Disjoint Cycles Problem on Euler Digraphs....Pages 250-262
Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs....Pages 263-274
Edge Elimination in TSP Instances....Pages 275-286
The Parameterized Complexity of the Rainbow Subgraph Problem....Pages 287-298
Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees....Pages 299-311
Graph-TSP from Steiner Cycles....Pages 312-323
A Characterization of Mixed Unit Interval Graphs....Pages 324-335
On the Number of Connected Sets in Bounded Degree Graphs....Pages 336-347
Parameterized Edge Hamiltonicity....Pages 348-359
Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs....Pages 360-371
The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results....Pages 372-383
Parameterized Algorithms for Graph Partitioning Problems....Pages 384-395
Between Treewidth and Clique-Width....Pages 396-407
A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs....Pages 408-419
Back Matter....Pages 421-422

✦ Subjects

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