K. Cattell et al., A SIMPLE LINEAR-TIME ALGORITHM FOR FINDING PATH-DECOMPOSITIONS OF SMALL WIDTH, Information processing letters, 57(4), 1996, pp. 197-203
Citations number
25
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
We described a simple algorithm running in linear time for each fixed
constant, k, that either establishes that the pathwidth of a graph C i
s greater than k, or finds a path-decomposition of G of width at most
O(2(k)). This provides a simple proof of the result by Bodlaender that
many families of graphs of bounded pathwidth can be recognized in lin
ear time.