Algorithmic Aspects of Graph Connectivity (Encyclopedia of Mathematics and its Applications, Series Number 123)

Publisher description: "Algorithmic Aspects of Graph Connectivity is the first comprehensive book on this central notion in graph and network theory, emphasizing its algorithmic aspects. Because of its wide applications in the fields of communication, transportation, and production, graph connectivity has made tremendous algorithmic progress under the influence of the theory of complexity and algorithms in modern computer science. The book contains various definitions of connectivity, including edge-connectivity and vertex-connectivity, and their ramifications, as well as related topics such as flows and cuts. The authors comprehensively discuss new concepts and algorithms that allow for quicker and more efficient computing, such as maximum adjacency ordering of vertices. Covering both basic definitions and advanced topics, this book can be used as a textbook in graduate courses in mathematical sciences, such as discrete mathematics, combinatorics, and operations research, and as a reference book for specialists in discrete mathematics and its applications." Cover......Page 1 Title Page......Page 6 Copyright......Page 7 Contents......Page 8 Preface......Page 10 Notation......Page 12 1.1 Preliminaries of Graph Theory......Page 18 1.2 Algorithms and Complexities......Page 30 1.3 Flows and Cuts......Page 37 1.4 Computing Connectivities......Page 51 1.5 Representations of Cut Structures......Page 62 1.6 Connectivity by Trees......Page 74 1.7 Tree Hypergraphs......Page 77 2.1 Spanning Subgraphs Preserving Connectivity......Page 82 2.2 MA Ordering......Page 90 2.3 3-Edge-Connected Components......Page 103 2.4 2-Approximation Algorithms for Connectivity......Page 117 2.5 Fast Maximum-Flow Algorithms......Page 124 2.6 Testing Chordality......Page 129 3.1 Pendent Pairs in MA Orderings......Page 131 3.2 A Minimum-Cut Algorithm......Page 134 3.3 s-Proper k-Edge-Connected Spanning Subgraphs......Page 136 3.4 A Hierarchical Structure of MA Orderings......Page 140 3.5 Maximum Flows Between a Pendent Pair......Page 144 3.6 A Generalization of Pendent Pairs......Page 147 3.7 Practically Efficient Minimum-Cut Algorithms......Page 148 4.1 Enumerating All Cuts......Page 154 4.2 Enumerating Small Cuts......Page 157 4.3 Enumerating Minimum Cuts......Page 162 4.4 Upper Bounds on the Number of Small Cuts......Page 166 5.1 Canonical Forms of Cactus Representations......Page 170 5.2 (s, t)-Cactus Representations......Page 188 5.3 Constructing Cactus Representations......Page 197 6 Extreme Vertex Sets......Page 208 6.1 Computing Extreme Vertex Sets in Graphs......Page 209 6.2 Algorithm for Dynamic Edges Incident to a Specified Vertex......Page 215 6.3 Optimal Contraction Ordering......Page 217 6.4 Minimum k-Subpartition Problem......Page 224 7.1 Preliminaries......Page 234 7.2 Edge Splitting in Weighted Graphs......Page 237 7.3 Edge Splitting in Multigraphs......Page 243 7.4 Other Splittings......Page 249 7.5 Detachments......Page 254 7.6 Applications of Splittings......Page 257 8 Connectivity Augmentation......Page 263 8.1 Increasing Edge-Connectivity by One......Page 264 8.2 Star Augmentation......Page 266 8.3 Augmenting Multigraphs......Page 269 8.4 Augmenting Weighted Graphs......Page 271 8.5 More on Augmentation......Page 293 9 Source Location Problems......Page 299 9.1 Source Location Problem Under Edge-Connectivity Requirements......Page 300 9.2 Source Location Problem Under Vertex-Connectivity Requirements......Page 312 10.1 Set Functions......Page 321 10.2 Minimizing Submodular and Posimodular Functions......Page 323 10.3 Extreme Subsets in Submodular and Posimodular Systems......Page 332 10.4 Optimization Problems over Submodular and Posimodular Systems......Page 337 10.5 Extreme Points of Base Polyhedron......Page 353 10.6 Minimum Transversal in Set Systems......Page 359 Bibliography......Page 374 Index......Page 388 Descripción del editor: "Algorithmic Aspects of Graph Connectivity is the first comprehensive book on this central notion in graph and network theory, emphasizing its algorithmic aspects. Because of its wide applications in the fields of communication, transportation, and production, graph connectivity has made tremendous algorithmic progress under the influence of the theory of complexity and algorithms in modern computer science. The book contains various definitions of connectivity, including edge-connectivity and vertex-connectivity, and their ramifications, as well as related topics such as flows and cuts. The authors thoroughly discuss new concepts and algorithms that allow for quicker and more efficient computing, such as maximum adjacency ordering of vertices. Covering both basic definitions and advanced topics, this book can be used as a textbook in graduate courses in mathematical sciences, such as discrete mathematics, combinatorics, and operations research, and as a reference book for specialists in discrete mathematics and its applications" (Cambridge University Press) Algorithmic Aspects Of Graph Connectivity Is The First Book That Thoroughly Discusses Graph Connectivity, A Central Notion In Graph And Network Theory, Emphasizing Its Algorithmic Aspects. This Book Contains Various Definitions Of Connectivity, Including Edge-connectivity, Vertex-connectivity, And Their Ramifications, As Well As Related Topics Such As Flows And Cuts. Covering Both Basic Definitions And Advanced Topics, This Book Can Be Used As A Textbook In Graduate Courses Of Mathematical Sciences (such As Discrete Mathematics, Combinatorics, And Operations Research) In Addition To Being An Important Reference Book For All Specialists Working In Discrete Mathematics And Its Applications.--jacket. Maximum Adjacency Ordering And Forest Decompositions -- Minimum Cuts -- Cut Enumeration -- Cactus Representations -- Extreme Vertex Sets -- Edge Splitting -- Connectivity Augmentation -- Source Location Problems -- Submodular And Posimodular Set Functions. Hiroshi Nagamochi, Toshihide Ibaraki. Includes Bibliographical References (p. 357-369) And Index.