##
**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.

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.

Reviewer: E.Ederle (München)

### MSC:

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 |