Graph Algorithms

by Shimon Even , Edited by Guy Even

• ISBN13: 9780521736534
• ISBN10: 0521736536
• Edition: 2nd
• Format: Paperback
• Copyright: 2011-09-19
• Publisher: Cambridge University Press

Summary

Shimon Even's Graph Algorithms, published in 1979, was a seminal introductory book on algorithms read by everyone engaged in the field. This thoroughly revised second edition, with a foreword by Richard M. Karp and notes by Andrew V. Goldberg, continues the exceptional presentation from the first edition and explains algorithms in a formal but simple language with a direct and intuitive presentation. The book begins by covering basic material, including graphs and shortest paths, trees, depth-first-search and breadth-first search. The main part of the book is devoted to network flows and applications of network flows, and it ends with chapters on planar graphs and testing graph planarity.

Author Biography

Shimon Even (1935-2004) was a pioneering researcher on graph algorithms and cryptography. He was a highly influential educator who played a major role in establishing computer science education in Israel at the Weizmann Institute and the Technion. He served as a source of professional inspiration and as a role model for generations of students and researchers. He is the author of Algorithmic Combinatorics [1973) and Graph Algorithms (1979).

Table of Contents

Foreword by	p. vii
Preface to the Second Edition	p. ix
Preface to the First Edition	p. xi
Paths in Graphs	p. 1
Introduction to Graph Theory	p. 1
Computer Representation of Graphs	p. 3
Euler Graphs	p. 6
De Bruijn Sequences	p. 9
Shortest-Path Algorithms	p. 11
Problems	p. 22
Trees	p. 29
Tree Definitions	p. 29
Minimum Spanning Tree	p. 31
Cayley's Theorem	p. 34
Directed Tree Definitions	p. 37
The Infinity Lemma	p. 39
Problems	p. 42
Depth-First Search	p. 46
DFS of Undirected Graphs	p. 46
Algorithm for Nonseparable Components	p. 52
DFS on Directed Graphs	p. 57
Strongly Connected Components of a Digraph	p. 58
Problems	p. 62
Ordered Trees	p. 65
Uniquely Decipherable Codes	p. 65
Positional Trees and Huffman's Optimization Problem	p. 69
Application of the Huffman Tree to Sort-by-Merge Techniques	p. 75
Catalan Numbers	p. 77
Problems	p. 82
Flow in Networks	p. 85
Introduction	p. 85
The Algorithm of Ford and Fulkerson	p. 87
The Dinitz Algorithm	p. 94
Networks with Upper and Lower Bounds	p. 102
Problems	p. 109
Notes by Andrew Goldberg	p. 115
Applications of Network Flow Techniques	p. 117
Zero-One Network Flow	p. 117
Vertex Connectivity of Graphs	p. 121
Connectivity of Digraphs and Edge Connectivity	p. 129
Maximum Matching in Bipartite Graphs	p. 135
Two Problems on PERT Digraphs	p. 137
Problems	p. 141
Planar Graphs	p. 146
Bridges and Kuratowski's Theorem	p. 146
Equivalence	p. 157
Euler's Theorem	p. 158
Duality	p. 159
Problems	p. 164
Testing Graph Planarity	p. 168
Introduction	p. 168
The Path Addition Algorithm of Hopcroft and Tarjan	p. 169
Computing an st-Numbering	p. 177
The Vertex Addition Algorithm of Lempel, Even,and Cederbaum	p. 179
Problems	p. 185
Index	p. 187
Table of Contents provided by Ingram. All Rights Reserved.