Width Parameters Beyond Tree-width and their Applications
Besides the successful concept of tree-width (see [H. Bodlaender, A. Koster: Combinatorial optimisation on graphs of bounded treewidth, ***** * this survey volume ******, 14 p.]) in the past years, many concepts and parameters measuring a similarity of structures to trees, or how a structure distinguishes from a tree, have been born and studied. These concepts and parameters proved to be useful tools for many applications, especially in the design of efficient algorithms. We present a novel view of contemporary developments of these “width” parameters in combinatorial structures that, besides traditional tree-width and derived dynamic programming schemes, leads to other usable parameters like branch-width,