Graph-Theoretic Concepts in Computer Science: 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers

✍ Scribed by Pinar Heggernes (eds.)

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

✦ Synopsis

This book constitutes revised selected papers from the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016, held in Istanbul, Turkey, in June 2016.
The 25 papers presented in this volume were carefully reviewed and selected from 74 submissions.The WG conferences aim to connect theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas of computer science and by extracting new graph problems from applications. Their goal is to present new research results and to identify and explore directions of future research.

✦ Table of Contents

Front Matter....Pages I-X
Sequences of Radius k for Complete Bipartite Graphs....Pages 1-12
Approximate Association via Dissociation....Pages 13-24
Geodetic Convexity Parameters for Graphs with Few Short Induced Paths....Pages 25-37
Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results....Pages 38-49
Finding Two Edge-Disjoint Paths with Length Constraints....Pages 50-61
Packing and Covering Immersion Models of Planar Subcubic Graphs....Pages 62-73
Parameterized Power Vertex Cover....Pages 74-84
Induced Separation Dimension....Pages 85-96
Tight Bounds for Gomory-Hu-like Cut Counting....Pages 97-108
Eccentricity Approximating Trees....Pages 109-120
Drawing Planar Graphs with Prescribed Face Areas....Pages 121-132
Vertex Cover Structural Parameterization Revisited....Pages 133-144
On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators....Pages 145-157
Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability....Pages 158-170
On Edge Intersection Graphs of Paths with 2 Bends....Pages 171-182
Almost Induced Matching: Linear Kernels and Parameterized Algorithms....Pages 183-194
Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property....Pages 195-206
Harmonious Coloring: Parameterized Algorithms and Upper Bounds....Pages 207-219
On Directed Steiner Trees with Multiple Roots....Pages 220-232
Sequence Hypergraphs....Pages 233-244
On Subgraphs of Bounded Degeneracy in Hypergraphs....Pages 245-256
Back Matter....Pages 257-268
....Pages 269-281

✦ Subjects

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