DEPTH-BOUNDED SEARCH TREES
Rolf Niedermeier · 2006
Abstract This chapter presents the second very basic design technique for fixed-parameter algorithms: depth-bounded search trees. It starts with simple observations and some basic definitions and facts, including recurrences and branching vectors as a tool for analysing search tree sizes. It continues giving several specific search tree results, including outlines of problems such as Cluster Editing, Vertex Cover, Hitting Set, Closest String, and Dominating Set in Planar Graphs. Moreover, it discusses how to interleave search tree and kernelization procedures to further speed up computation, and it proposes a way to generate automatically search trees (also analysing their sizes) using Cluster Deletion as an illustrative example.