عنوان

Data structures and algorithms. 2, Graph algorithms and NP-completeness

3642698972

9783642698972

b572868

Data structures and algorithms. 2, Graph algorithms and NP-completeness

[Book]

Kurt Mehlhorn.

Berlin ; New York

Springer-Verlag

1984

(xii, 260 pages) : illustrations

EATCS monographs on theoretical computer science, 2.

Rev. translation of: Effiziente Algorithmen. Stuttgart : Teubner, 1977.

Vol. 2: Graph Algorithms and NP-Completeness --; IV. Algorithms on Graphs --; 1. Graphs and their Representation in a Computer --; 2. Topological Sorting and the Representation Problem --; 3. Transitive Closure of Acyclic Digraphs --; 4. Systematic Exploration of a Graph --; 5. A Close Look at Depth First Search --; 6. Strongly-Connected and Biconnected Components of Directed and Undirected Graphs --; 7. Least Cost Paths in Networks --; 8. Minimum Spanning Trees --; 9. Maximum Network Flow and Applications --; 10. Planar Graphs --; 11. Exercises --; 12. Bibliographic Notes --; V. Path Problems in Graphs and Matrix Multiplication --; 1. General Path Problems --; 2. Two Special Cases: Least Cost Paths and Transitive Closure --; 3. General Path Problems and Matrix Multiplication --; 4. Matrix Multiplication in a Ring --; 5. Boolean Matrix Multiplication and Transitive Closure --; 6. (Min, +)-Product of Matrices and Least Cost Paths --; 7. A Lower Bound on the Monotone Complexity of Matrix Multiplication --; 8. Exercises --; 9. Bibliographic Notes --; VI. NP-Completeness --; 1. Turing Machines and Random Access Machines --; 2. Problems, Languages and Optimization Problems --; 3. Reductions and NP-complete Problems --; 4. The Satisfiability Problem is NP-complete --; 5. More NP-complete Problems --; 6. Solving NP-complete Problems --; 7. Approximation Algorithms --; 8. The Landscape of Complexity Classes --; 9. Exercises --; 10. Bibliographic Notes --; IX. Algorithmic Paradigms.

Algorithms.

Computer programming.

Data structures (Computer science)

Kurt Mehlhorn.

Kurt Mehlhorn

[Book]

Y