Graph Theory, Computational Intelligence and Thought

Springer - Graph-Theoretic Concepts in Computer Science (02-2010) (ATTiCA)......Page 0
Preface......Page 4
Conference Organization......Page 5
Table of Contents......Page 8
Introduction......Page 11
Art Gallery Problems......Page 12
Partition into Rectangles......Page 13
Minimum Diameter Clustering......Page 15
Bend Minimization......Page 17
Mesh Stripification......Page 18
Angle Optimization of Tilings......Page 20
Metric Embedding into Stars......Page 21
Conclusions......Page 23
Introduction......Page 27
Graph Decompositions, Graph Minors......Page 28
Grad and Expansion......Page 30
Orientations with Small In-Degree......Page 33
Low Tree-Width and Low-Tree-Depth Coloring......Page 36
Testing Graph Properties......Page 38
$\\Sigma$1-Properties......Page 39
First-Order Properties......Page 40
Motivation: Community Structure in Networks......Page 43
Q(G;x,y) as a Graph Polynomial......Page 44
Distinguishing Power......Page 45
Subset Expansion and Definability in Logic......Page 46
The Universality Property of Q( G;x,y)......Page 47
Vertex Eliminations vs Edge Elimination......Page 49
Parameterized Complexity......Page 50
Conclusions and Open Problems......Page 51
Introduction......Page 54
The Two Exact Algorithms......Page 56
Closed Trails of Low Degeneracy and Ordering......Page 57
Branching on Vertices of Low Degree......Page 58
An O*(1.6818n) Time Algorithm That Uses Exponential Space......Page 59
Conclusions......Page 62
Introduction......Page 64
Preliminaries......Page 65
A Local Improvement Algorithm......Page 68
Running Time Analysis......Page 70
Approximation Ratio Analysis......Page 71
Introduction......Page 76
Construction of a Low Port Tree with Cost O(n)......Page 77
Outline of the Algorithm......Page 78
Analysis......Page 82
Introduction......Page 87
Preliminaries......Page 88
Three Representations of Interval Graphs......Page 89
Linear-Time Equivalence of PQ-Representation and MD-Representation......Page 91
Focus on the Key Node......Page 92
Dynamic Characterisation of Interval Graphs......Page 93
Overview of the Algorithm and Complexity......Page 95
Introduction......Page 98
Parameterized Hardness Results......Page 100
Minimum Label Maximum Matching (MLMM)......Page 101
Minimum Label Edge Dominating Set (MLEDS)......Page 106
Concluding Remarks......Page 108
Introduction......Page 110
Observations......Page 112
Reduction Rules......Page 113
The Algorithm......Page 114
Conclusion and Future Research......Page 120
Introduction......Page 122
Preliminaries......Page 123
Exact Algorithm for Distortion......Page 124
Dealing with Many Buckets......Page 125
Dealing with Few Buckets......Page 127
Concluding Remarks and Open Problems......Page 130
Introduction......Page 132
Applications......Page 134
Related Work......Page 135
Partitioning Phase......Page 136
Analysis......Page 137
NP-Completeness......Page 139
An O(logn)-approximation for Hypo-coloring......Page 140
($ igma, \\rho$)-Domination......Page 143
Notation and Overview of Our Results......Page 145
W[1]-Hardness......Page 146
W[1]-Membership......Page 147
Complexity of the ($ igma, \\rho$)-Dominating Set of Size at least n-k Problems......Page 149
Complexity for the Case $ igma, \\rho \\epsilon$ {EVEN,ODD}......Page 150
Complexity of the ($ igma, \\rho$)-Dominating Set of Size (at most) k Problem for Sparse Graphs......Page 151
Introduction......Page 153
Insightful Observations......Page 154
FVS and FHS in Planar Graphs with Minimum Degree 3......Page 156
Diameter of Polytopes......Page 159
Approximation Schemes for FHS and Connected FVS......Page 160
Introduction......Page 164
Graphs, First-Order Logic and Locality......Page 166
Distributed Evaluation of FO......Page 168
Bounded Degree Networks......Page 169
Planar Networks......Page 170
Beyond FO Properties......Page 172
Conclusion......Page 173
Introduction......Page 176
Preliminaries......Page 177
Module-Composed Graphs......Page 178
How to Find Module-Sequences......Page 179
Easy Problems on Module-Composed Graphs......Page 181
Characterizations for Independent Module-Composed Graphs......Page 182
How to Find Independent Module-Sequences......Page 184
Easy Problems on Independent Module-Composed Graphs......Page 185
Conclusions......Page 186
Introduction......Page 188
The $\\downarrow$  Operation on Sets......Page 190
The High-Level Algorithm......Page 192
Realizing the Set Operations......Page 194
An Implementation in D......Page 196
Introduction......Page 200
The k-Disjoint-Paths Problem......Page 202
Shortest k-Disjoint Paths......Page 204
A Speedup......Page 205
Hardness of the Disjoint-Paths Problem......Page 209
Introduction......Page 212
Definitions and Notations......Page 214
Preliminaries......Page 215
Edge Coloring......Page 216
The Local Distributed Algorithm......Page 219
The Improved Algorithm......Page 222
Introduction......Page 224
Preliminaries......Page 225
Rank-Width of Digraphs......Page 226
Bi-Partitive Families......Page 227
Quotient Graphs......Page 229
Digraphs of GF(4)-Rank-Width 1......Page 231
Concluding Remarks......Page 233
Introduction......Page 236
Bipartite, Planar, Triangle-Free Graphs......Page 238
Global Connectivity......Page 240
Local Connectivity......Page 243
Even Degrees and Eulerian Graphs......Page 244
Acyclic and Almost Acyclic Graphs......Page 245
Introduction and Results......Page 248
Hardness Results......Page 250
Squares of Strongly Chordal Split Graphs......Page 254
Powers versus Girth......Page 255
Conclusion and Open Problems......Page 257
Introduction......Page 260
Reducing the Problem......Page 262
Case $\\Delta$=3, C=4......Page 264
Case $\\Delta$ ≥ 4 Even......Page 266
General Upper Bound......Page 267
Optimal Construction for Graphs with a Perfect Matching......Page 268
Improved Lower Bounds......Page 269
Conclusions......Page 270
Introduction......Page 272
Preliminaries......Page 273
Complexity......Page 274
Cliques......Page 275
Bounds on the Oriented Injective Chromatic Number......Page 276
Oriented Injective Colourings of Trees......Page 279
Introduction......Page 283
Preliminaries......Page 285
Definition of Chordal Digraphs and First Results......Page 286
Two Classes of Chordal Digraphs......Page 289
Chordal Semi-complete Digraphs......Page 290
Conclusion......Page 293
Introduction......Page 295
A New Intersection Model for Tolerance Graphs......Page 298
A Canonical Representation of Tolerance Graphs......Page 301
Weighted Independent Set Algorithm in O(n2)......Page 303
Conclusions and Further Research......Page 304
Introduction......Page 306
Preliminaries......Page 307
Polynomial-Time Algorithm for Chain Graphs......Page 308
Polynomial-Time Algorithm for Cochain Graphs and Threshold Graphs......Page 312
Hardness Results......Page 313
Introduction......Page 318
Preliminaries......Page 320
d-Domination Games......Page 321
Monotonicity of Domination Games......Page 323
Complexity of Domination Games......Page 325
Games on Hypergraphs and Visible Robbers......Page 327
Introduction......Page 330
Cycles and Paths in Distance Graphs......Page 332
Connectivity and Diameter in Distance Graphs......Page 335
Introduction......Page 339
Preliminaries......Page 340
Tents......Page 341
Edge-Path with Respect to a Hole......Page 342
Shortcuts of a Hole......Page 343
$\\tau$-BFS......Page 345
The Algorithm......Page 346
$\\tau$-Path......Page 347
Complexity......Page 348
Further Research......Page 349
Introduction......Page 351
Preliminaries......Page 354
Finding Induced Paths of Given Parity......Page 355
Preprocessing the Input Graph G......Page 356
G\'\' Is Not Perfect......Page 357
G\'\' Is Perfect......Page 359
Finding Induced Paths of Given Parity from s to t in G......Page 360
Conclusions and Open Problems......Page 361
Author Index......Page 363