A SIMPLE LINEAR-TIME ALGORITHM FOR FINDING PATH-DECOMPOSITIONS OF SMALL WIDTH

Authors
CATTELL K DINNEEN MJ FELLOWS MR
Citation
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
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
57
Issue
4
Year of publication
1996
Pages
197 - 203
Database
ISI
SICI code
0020-0190(1996)57:4<197:ASLAFF>2.0.ZU;2-A
Abstract
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.