A Guide to Graph Algorithms
- Length: 355 pages
- Edition: 1
- Language: English
- Publisher: Springer
- Publication Date: 2022-02-23
- ISBN-10: 9811663491
- ISBN-13: 9789811663499
- Sales Rank: #2394736 (See Top 100 Books)
This book A Guide to Graph Algorithms offers high-quality content in the research area of graph algorithms and explores the latest developments in graph algorithmics. The reader will gain a comprehensive understanding of how to use algorithms to explore graphs. It is a collection of texts that have proved to be trend setters and good examples of that. The book aims at providing the reader with a deep understanding of the structural properties of graphs that are useful for the design of efficient algorithms. These algorithms have applications in finite state machine modelling, social network theory, biology, and mathematics. The book contains many exercises, some up at present-day research-level. The exercises encourage the reader to discover new techniques by putting things in a clear perspective. A study of this book will provide the reader with many powerful tools to model and tackle problems in real-world scenarios.
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
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.