Combinatorial algorithms. Transl. from the Czech by Jiří Adámek. (English) Zbl 0731.68084

Bristol etc.: Adam Hilger. xi, 270 p. £25.00 (1990).
The book is devoted to the solution of problems presented by the theory of graphs.
After a concise introduction to the theory of graphs and to models of computation, important techniques necessary for designing algorithms for graph processing (data structures, graph searching and sorting) are presented.
The basis of the book is formed by three chapters, one describing problems for which good algorithms are known (“Problems solvable in polynomial time”), the other describing problems for which no good algorithms are known and explaining the reasons for this (“NP-complete problems”) and the third oriented to practical problems introducing heuristic and approximate methods for the solution of some of the NP- complete problems. A last chapter studies the probabilistic analysis of some of the presented algorithms.
The book, mainly discussing the question of computational complexity of problems of graph theory is directed to students of computer science as well as to programmers and workers in the computer area.


68R05 Combinatorics in computer science
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks