Algorithmic Aspects of Graph Connectivity
This book is devoted to graph connectivity, an important notion in graph theory with numerous practical applications. It gives a rich theoretical background; however, a strong emphasis is put on algorithms and their effectiveness. After the introductory chapter, the next chapters deal with maximum adjacency ordering and its applications (fast maximum flow algorithms or chordality testing; minimum cuts; cut enumeration; cactus representations; extreme vertex sets; edge splitting; connectivity augmentation; source location problems; and submodular and posimodular functions). In each chapter, the authors present a wide overview of algorithms, including the classical ones as well as recent effective methods. The book is comprehensive and detailed. A general insight in the studied topics is useful to the reader, although the first chapter of the book contains a brief introduction and establishes all the used notions. The book can be useful as a reference book for a specialist whose work relates to graph theory but it can also be used as a textbook for advanced courses in discrete mathematics, graph-theory algorithms and optimisation.