A Guide to Graph Algorithms

Contents
Preface
About the authors
Acknowledgments
Graphs
1.1 Isomorphic Graphs
1.2 Representing graphs
1.3 Neighborhoods
1.4 Connectedness
1.5 Induced Subgraphs
1.6 Paths and Cycles
1.7 Complements
1.8 Components
1.8.1 Rem ' s Algorithm
1.9 Separators
1.10 Trees
1.11 Bipartite Graphs
1.12 Linegraphs
1.13 Cliques and Independent Sets
1.14 On Notations
Algorithms
2.1 Finding and counting small induced subgraphs
2.2 Bottleneck domination
2.3 The Bron & Kerbosch Algorithm
2.3.1 A Timebound for the B & K – Algorithm
2.4 Total Order!
2.4.1 Hypergraphs
2.4.2 Problem Reductions
2.5 NP – Completeness
2.5.1 Equivalence covers of splitgraphs
Chromatic index
2.6 Lov asz Local Lemma
2.6.1 Bounds on dominating sets
2.6.2 The Moser & Tardos algorithm
2.6.3 Logs and witness trees
2.6.4 A Galton Watson branching process
2.7 Szemer edi's Regularity Lemma
2.7.1 Construction of regular partitions
2.8 Edge thickness and stickiness
Computing stickiness
2.9 Clique Separators
2.9.1 Feasible Partitions
2.9.2 Intermezzo
2.9.3 Another Intermezzo: Trivially perfect graphs
2.10 Vertex ranking
2.10.1 Permutation graphs
2.10.2 Separators in permutation graphs
2.10.3 Vertex ranking of permutation graphs
2.11 Cographs
2.11.1 Switching cographs
2.12 Parameterized Algorithms
2.13 The bounded search technique
2.13.1 Vertex cover
2.13.2 Edge dominating set
2.13.3 Feedback vertex set
2.13.4 Further reading
References
2.14 Matchings
2.15 Independent Set in Claw - Free Graphs
2.15.1 The Blossom Algorithm
2.15.2 Minty ' s Algorithm
2.15.3 A Cute Lemma
2.15.4 Edmonds ' Graph
2.16 Dominoes
2.17 Triangle partition of planar graphs
The dual
The triangle partition algorithm
Graphs without separating triangles
Graphs with separating triangles
2.17.1 Intermezzo: PQ – trees
2.18 Games
2.18.1 Snake
2.18.2 Grundy values
2.18.3 De Bruijn's game
2.18.4 Poset games
2.18.5 Coin - turning games
2.18.6 NIM - multiplication
2.18.7 P3 - Games
2.18.8 Chomp
Problem Formulations
3.1 Graph Algebras
3.2 Monadic Second – Order Logic
3.2.1 Sentences and Expressions
3.2.2 Quanti cation over Subsets of Edges
Recent Trends
4.1 Triangulations
4.1.1 Chordal Graphs
4.1.2 Clique – Trees
4.2 Treewidth
Treewidth of Claw – Free Graphs
4.2.1 Treewidth and brambles
Further reading
4.2.2 Tree - decompositions
4.2.3 Example: Steiner tree
Partitions of a set
Steiner trees
Processing the tree - decomposition
Process at a start node
Process at an introduce node
Process at a forget node
Process at a join node
Conclusion
Must - reads on Steiner trees
4.2.4 Treewidth of Circle Graphs
Crossing Separators
Minimal Separators in Circle Graphs
An algorithm to compute the treewidth of circle graphs
4.3 On the treewidth of planar graphs
4.3.1 Antipodalities
4.3.2 Tilts and slopes
4.3.3 Bond carvings
4.3.4 Carvings and antipodalities
4.4 Tree - degrees of graphs
4.4.1 Intermezzo: Interval graphs
4.5 Modular decomposition
4.5.1 Modular decomposition tree
4.5.2 A linear - time modular decomposition
Refinement
Promotion
Assembly
Conclusion
Further reading
4.5.3 Exercise
4.6 Rankwidth
4.6.1 Distance hereditary - graphs
4.6.2 Intermezzo: Perfect graphs
4.6.3 χ Boundedness
4.6.4 Governed decompositions
4.6.5 Forward Ramsey splits
4.6.6 Factorization of trees
4.6.7 Kruskalian decompositions
4.6.8 Exercise
4.7 Clustered coloring
4.7.1 Bandwidth and BFS - trees with few leaves
4.7.2 Connected partitions
4.7.3 A decomposition of Kt minor free graphs
4.7.4 Further reading
4.8 Well Quasi Orders
4.8.1 Higman's Lemma
4.8.2 Kruskal's Theorem
4.8.3 Gap embeddings
4.9 Threshold graphs and threshold - width
4.9.1 Threshold width
4.9.2 On the complexity of threshold - width
4.9.3 A fixed - parameter algorithm for threshold - width
4.10 Black and white - coloring
4.10.1 The complexity of black and white - coloring
4.11 k – Cographs
4.11.1 Recognition of k – Cographs
4.11.2 Recognition of k – Cographs — revisited
4.11.3 Treewidth of Cographs
4.12 Minors
4.12.1 The Graph Minor Theorem
4.13 General Partition Graphs
4.14 Tournaments
4.14.1 Tournament games
4.14.2 Trees in tournaments
Well - rooted trees
Further reading
4.14.3 Immersions in tournaments
What happened earlier ..
Linked layouts
Gap sequences
Marches
Codewords
Encoding
4.14.4 Domination in tournaments
4.15 Immersions
4.15.1 Intermezzo: Topological minors
Further reading on topological minors:
4.15.2 Strong immersions in series - parallel digraphs
4.15.3 Intermezzo on 2 - trees
4.15.4 Series parallel - triples
Parallel compositions
F - Series parallel trees
Truncations and portraits
4.15.5 A well quasi - order for one way series parallel - triples
4.15.6 Series parallel separations
4.15.7 Coda
4.15.8 Exercise
4.16 Asteroidal sets
4.16.1 AT - free graphs
4.16.2 Independent set in AT-free graphs
4.16.3 Exercise
4.16.4 Bandwidth of AT-free graphs
4.16.5 Dominating pairs
4.16.6 Antimatroids
4.16.7 Totally balanced matrices
Further reading
4.16.8 Triangle graphs
4.17 Sensitivity
4.17.1 What happened earlier ...
4.17.2 Cauchy's interlace lemma
4.17.3 Hypercubes
The proof of the hypercube theorem
4.17.4 Möbius inversion
4.17.5 The equivalence theorem
4.17.6 Further reading
4.18 Homomorphisms
4.18.1 Retracts
4.18.2 Retracts in threshold graphs
4.18.3 Retracts in cographs
4.19 Products
4.19.1 Categorical products of cographs
4.19.2 Tensor capacity
4.19.3 Cartesian products
Independence domination
4.19.4 Independence domination in cographs
4.19.5 e(Kn x Kn)
The tensor product Kn x Kn
4.20 Outerplanar Graphs
4.20.1 k – Outerplanar Graphs
4.20.2 Courcelle ' s Theorem
4.20.3 Approximations for Planar Graphs
4.20.4 Independent Set in Planar Graphs
4.21 Graph isomorphism
Must - reads on graph isomorphism
Bibliography
Index