Many problems that are computationally hard on general graphs (e.\,g.\ Hamiltonian circuit, $k$-colorability) are trivial to handle efficiently on trees. \emph{Tree-de\-com\-po\-si\-tions}\index{tree-decomposition}, which decompose graphs into small subgraphs along trees, allow to generalize this to efficient algorithms on classes of tree-like graphs. \emph{Tree-width}\index{tree-width} ($\tw$\index{tw@$\tw$}) captures the property of being tree-like: The smaller the tree-width, the more tree-like the graph.
























































































Something far down to make the vertical scroll bar appear.