A Linear Algorithm for the Pathwidth of Trees
Petra Scheffler · 1990
The pathwidth is a graph parameter only recently studied but closely related to other characteristics of graphs like tree, band- or cutwidth, interval thickness or search number ([S]). The graphs considered here are finite, undirected and simple. First the preliminaries are given. Section 2 contains our main results on the pathwidth of trees, the basis for the algorithm described in section 3. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.