|
" Data structures and algorithms. 2, Graph algorithms and NP-completeness "
Kurt Mehlhorn.
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
752909
|
| Doc. No
|
:
|
b572868
|
| Main Entry
|
:
|
Kurt Mehlhorn.
|
| Title & Author
|
:
|
Data structures and algorithms. 2, Graph algorithms and NP-completeness\ Kurt Mehlhorn.
|
| Publication Statement
|
:
|
Berlin ; New York : Springer-Verlag, 1984
|
| Series Statement
|
:
|
EATCS monographs on theoretical computer science, 2.
|
| Page. NO
|
:
|
(xii, 260 pages) : illustrations
|
| ISBN
|
:
|
3642698972
|
|
|
:
|
: 9783642698972
|
| Notes
|
:
|
Rev. translation of: Effiziente Algorithmen. Stuttgart : Teubner, 1977.
|
| Contents
|
:
|
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.
|
| Subject
|
:
|
Algorithms.
|
| Subject
|
:
|
Computer programming.
|
| Subject
|
:
|
Data structures (Computer science)
|
| LC Classification
|
:
|
QA76.9.D35K878 1984
|
| Added Entry
|
:
|
Kurt Mehlhorn
|
| |