Advances in Graph Algorithms

This is a book about some currently popular topics such as exponential algorithms, fixed-parameter algorithms and algorithms using decomposition trees of graphs. Especially for this last topic the authors found it necessary to include a chapter on graph classes.

The authors prepared this book as a course textbook for our students in Taiwan. The aim was to write a book about some currently popular topics such as exponential algorithms, fixed-parameter algorithms and algorithms using decomposition trees of graphs. Especially for this last topic the authors found it necessary to include a chapter on graph classes. The chapter on decomposition trees includes some basics of the graph minor theory and such topics as tree decompositions and rank decompositions. To explain these concepts we found it beneficial to include a chapter which explains the classes of chordal graphs and distance-hereditary graphs.

After each chapter we included some basic exercises. For experienced students these exercises are probably too easy. We made the decision to concentrate on elementary exercises in order not to distract the student too much from the main topics. The exercises are primarily meant as a check for the students that they understand the material of the chapter.