Algorithms for graphs of small treewidth.

*(English)*Zbl 0937.68092
Utrecht: Univ. Utrecht. iv, 246 p. (1997).

This book describes graph algorithms which utilize the tree decomposition of a graph. A tree decomposition of width \(k\) of a graph \(G\) is a tree \(T\) associated with \(G\) in which each vertex represents a subgraph of \(G\) with at most \(k+1\) vertices such that all vertices and edges of \(G\) are represented in at least one vertex of \(T\) and for each vertex \(v\) of \(G\) the vertices of \(T\) in which \(v\) is represented form a subtree of \(T\).

If \(T\) is a path, such a decomposition is called a path decomposition of \(G\), again of width \(k\). The treewidth (or pathwidth) of \(G\) is the minimum integer \(k\) such that there exists a tree decomposition (or path decomposition respectively of \(G\) of width \(k\)). Various problems which are hard for graphs in general may be much more easily solved for graphs with a small treewidth. This book describes corresponding algorithms.

The first chapter is “Introduction”, the second chapter is “Preliminaries”. The third chapter “The structure of partial two-paths” follows. The fourth chapter “DNA physical mapping” concerns applications in molecular biology, namely recognizing the structure of DNA molecules. Following chapters study reduction algorithms (5. “Reduction algorithms”, 6. “Constructive reduction algorithms”, 7. “Applications of reduction algorithms”).

A reduction algorithm is given by a finite set of reduction rules and a finite set of graphs. The reduction rules yield certain modifications of a graph. If after performing these rules the finally resulting graph belongs to the given set of graphs, then the answer to the investigated question is affirmative, otherwise it is negative. Constructive reduction algorithms are obtained from these algorithms by a certain modification. At the problem, whether some object (e.g. Hamiltonian circuit) exists, they give not only the answer yes or no, but an explicit construction of that object. The following two chapters concern rather special concepts (8. “Parallel algorithms for series-parallel graphs”, 9. “Parallel algorithms for treewidth two”). The last chapter is 10. “Conclusions”. Then Appendix A follows; it gives a survey of graph problems which are treated within the book. At the end there is its summary and the author’s biography, both in Dutch.

The today trend of the graph theory is such that not only theoretical results are needed, but there is also a growing interest in graph algorithms and in books describing them. And this book is one of them and may be a useful tool for a reader. The reader is expected to have a good knowledge of the graph theory.

If \(T\) is a path, such a decomposition is called a path decomposition of \(G\), again of width \(k\). The treewidth (or pathwidth) of \(G\) is the minimum integer \(k\) such that there exists a tree decomposition (or path decomposition respectively of \(G\) of width \(k\)). Various problems which are hard for graphs in general may be much more easily solved for graphs with a small treewidth. This book describes corresponding algorithms.

The first chapter is “Introduction”, the second chapter is “Preliminaries”. The third chapter “The structure of partial two-paths” follows. The fourth chapter “DNA physical mapping” concerns applications in molecular biology, namely recognizing the structure of DNA molecules. Following chapters study reduction algorithms (5. “Reduction algorithms”, 6. “Constructive reduction algorithms”, 7. “Applications of reduction algorithms”).

A reduction algorithm is given by a finite set of reduction rules and a finite set of graphs. The reduction rules yield certain modifications of a graph. If after performing these rules the finally resulting graph belongs to the given set of graphs, then the answer to the investigated question is affirmative, otherwise it is negative. Constructive reduction algorithms are obtained from these algorithms by a certain modification. At the problem, whether some object (e.g. Hamiltonian circuit) exists, they give not only the answer yes or no, but an explicit construction of that object. The following two chapters concern rather special concepts (8. “Parallel algorithms for series-parallel graphs”, 9. “Parallel algorithms for treewidth two”). The last chapter is 10. “Conclusions”. Then Appendix A follows; it gives a survey of graph problems which are treated within the book. At the end there is its summary and the author’s biography, both in Dutch.

The today trend of the graph theory is such that not only theoretical results are needed, but there is also a growing interest in graph algorithms and in books describing them. And this book is one of them and may be a useful tool for a reader. The reader is expected to have a good knowledge of the graph theory.

Reviewer: Bohdan Zelinka (Liberec)

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

68Q25 | Analysis of algorithms and problem complexity |

05C85 | Graph algorithms (graph-theoretic aspects) |

90C35 | Programming involving graphs or networks |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |