Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers

3642114083......Page 1
Lecture Notes in Computer Science 5911......Page 2
Graph-Theoretic
Concepts
in Computer Science
35th InternationalWorkshop, WG 2009
Montpellier, France, June 24-26, 2009
Revised Papers......Page 3
Preface......Page 5
Conference Organization......Page 6
Table of Contents......Page 9
Introduction......Page 12
Art Gallery Problems......Page 13
Partition into Rectangles......Page 14
Minimum Diameter Clustering......Page 16
Bend Minimization......Page 18
Mesh Stripification......Page 19
Angle Optimization of Tilings......Page 21
Metric Embedding into Stars......Page 22
Conclusions......Page 24
Introduction......Page 28
Graph Decompositions, Graph Minors......Page 29
Grad and Expansion......Page 31
Orientations with Small In-Degree......Page 34
Low Tree-Width and Low-Tree-Depth Coloring......Page 37
Testing Graph Properties......Page 39
$\Sigma$1-Properties......Page 40
First-Order Properties......Page 41
Motivation: Community Structure in Networks......Page 44
Q(G;x,y) as a Graph Polynomial......Page 45
Distinguishing Power......Page 46
Subset Expansion and Definability in Logic......Page 47
The Universality Property of Q( G;x,y)......Page 48
Vertex Eliminations vs Edge Elimination......Page 50
Parameterized Complexity......Page 51
Conclusions and Open Problems......Page 52
Introduction......Page 55
The Two Exact Algorithms......Page 57
Closed Trails of Low Degeneracy and Ordering......Page 58
Branching on Vertices of Low Degree......Page 59
An O*(1.6818n) Time Algorithm That Uses Exponential Space......Page 60
Conclusions......Page 63
Introduction......Page 65
Preliminaries......Page 66
A Local Improvement Algorithm......Page 69
Running Time Analysis......Page 71
Approximation Ratio Analysis......Page 72
Introduction......Page 77
Construction of a Low Port Tree with Cost O(n)......Page 78
Outline of the Algorithm......Page 79
Analysis......Page 83
Introduction......Page 88
Preliminaries......Page 89
Three Representations of Interval Graphs......Page 90
Linear-Time Equivalence of PQ-Representation and MD-Representation......Page 92
Focus on the Key Node......Page 93
Dynamic Characterisation of Interval Graphs......Page 94
Overview of the Algorithm and Complexity......Page 96
Introduction......Page 99
Parameterized Hardness Results......Page 101
Minimum Label Maximum Matching (MLMM)......Page 102
Minimum Label Edge Dominating Set (MLEDS)......Page 107
Concluding Remarks......Page 109
Introduction......Page 111
Observations......Page 113
Reduction Rules......Page 114
The Algorithm......Page 115
Conclusion and Future Research......Page 121
Introduction......Page 123
Preliminaries......Page 124
Exact Algorithm for Distortion......Page 125
Dealing with Many Buckets......Page 126
Dealing with Few Buckets......Page 128
Concluding Remarks and Open Problems......Page 131
Introduction......Page 133
Applications......Page 135
Related Work......Page 136
Partitioning Phase......Page 137
Analysis......Page 138
NP-Completeness......Page 140
An O(logn)-approximation for Hypo-coloring......Page 141
($ igma, \rho$)-Domination......Page 144
Notation and Overview of Our Results......Page 146
W[1]-Hardness......Page 147
W[1]-Membership......Page 148
Complexity of the ($ igma, \rho$)-Dominating Set of Size at least n-k Problems......Page 150
Complexity for the Case $ igma, \rho \epsilon$ {EVEN,ODD}......Page 151
Complexity of the ($ igma, \rho$)-Dominating Set of Size (at most) k Problem for Sparse Graphs......Page 152
Introduction......Page 154
Insightful Observations......Page 155
FVS and FHS in Planar Graphs with Minimum Degree 3......Page 157
Diameter of Polytopes......Page 160
Approximation Schemes for FHS and Connected FVS......Page 161
Introduction......Page 165
Graphs, First-Order Logic and Locality......Page 167
Distributed Evaluation of FO......Page 169
Bounded Degree Networks......Page 170
Planar Networks......Page 171
Beyond FO Properties......Page 173
Conclusion......Page 174
Introduction......Page 177
Preliminaries......Page 178
Module-Composed Graphs......Page 179
How to Find Module-Sequences......Page 180
Easy Problems on Module-Composed Graphs......Page 182
Characterizations for Independent Module-Composed Graphs......Page 183
How to Find Independent Module-Sequences......Page 185
Easy Problems on Independent Module-Composed Graphs......Page 186
Conclusions......Page 187
Introduction......Page 189
The $\downarrow$ Operation on Sets......Page 191
The High-Level Algorithm......Page 193
Realizing the Set Operations......Page 195
An Implementation in D......Page 197
Introduction......Page 201
The k-Disjoint-Paths Problem......Page 203
Shortest k-Disjoint Paths......Page 205
A Speedup......Page 206
Hardness of the Disjoint-Paths Problem......Page 210
Introduction......Page 213
Definitions and Notations......Page 215
Preliminaries......Page 216
Edge Coloring......Page 217
The Local Distributed Algorithm......Page 220
The Improved Algorithm......Page 223
Introduction......Page 225
Preliminaries......Page 226
Rank-Width of Digraphs......Page 227
Bi-Partitive Families......Page 228
Quotient Graphs......Page 230
Digraphs of GF(4)-Rank-Width 1......Page 232
Concluding Remarks......Page 234
Introduction......Page 237
Bipartite, Planar, Triangle-Free Graphs......Page 239
Global Connectivity......Page 241
Local Connectivity......Page 244
Even Degrees and Eulerian Graphs......Page 245
Acyclic and Almost Acyclic Graphs......Page 246
Introduction and Results......Page 249
Hardness Results......Page 251
Squares of Strongly Chordal Split Graphs......Page 255
Powers versus Girth......Page 256
Conclusion and Open Problems......Page 258
Introduction......Page 261
Reducing the Problem......Page 263
Case $\Delta$=3, C=4......Page 265
Case $\Delta$ ≥ 4 Even......Page 267
General Upper Bound......Page 268
Optimal Construction for Graphs with a Perfect Matching......Page 269
Improved Lower Bounds......Page 270
Conclusions......Page 271
Introduction......Page 273
Preliminaries......Page 274
Complexity......Page 275
Cliques......Page 276
Bounds on the Oriented Injective Chromatic Number......Page 277
Oriented Injective Colourings of Trees......Page 280
Introduction......Page 284
Preliminaries......Page 286
Definition of Chordal Digraphs and First Results......Page 287
Two Classes of Chordal Digraphs......Page 290
Chordal Semi-complete Digraphs......Page 291
Conclusion......Page 294
Introduction......Page 296
A New Intersection Model for Tolerance Graphs......Page 299
A Canonical Representation of Tolerance Graphs......Page 302
Weighted Independent Set Algorithm in O(n2)......Page 304
Conclusions and Further Research......Page 305
Introduction......Page 307
Preliminaries......Page 308
Polynomial-Time Algorithm for Chain Graphs......Page 309
Polynomial-Time Algorithm for Cochain Graphs and Threshold Graphs......Page 313
Hardness Results......Page 314
Introduction......Page 319
Preliminaries......Page 321
d-Domination Games......Page 322
Monotonicity of Domination Games......Page 324
Complexity of Domination Games......Page 326
Games on Hypergraphs and Visible Robbers......Page 328
Introduction......Page 331
Cycles and Paths in Distance Graphs......Page 333
Connectivity and Diameter in Distance Graphs......Page 336
Introduction......Page 340
Preliminaries......Page 341
Tents......Page 342
Edge-Path with Respect to a Hole......Page 343
Shortcuts of a Hole......Page 344
$\tau$-BFS......Page 346
The Algorithm......Page 347
$\tau$-Path......Page 348
Complexity......Page 349
Further Research......Page 350
Introduction......Page 352
Preliminaries......Page 355
Finding Induced Paths of Given Parity......Page 356
Preprocessing the Input Graph G......Page 357
G'' Is Not Perfect......Page 358
G'' Is Perfect......Page 360
Finding Induced Paths of Given Parity from s to t in G......Page 361
Conclusions and Open Problems......Page 362
Author Index......Page 364