Bounded Persistence Pathwidth

Downey, R.G. and McCartin, C.

    The role of graph width metrics, such as treewidth, pathwidth, and cliquewidth, is now seen as central in both algorithm design and the delineation of what is algorithmically possible. In this article we introduce a new, related, parameter for graphs, persistence. A path decomposition of width k, in which every vertex of the underlying graph belongs to at most l nodes of the path, has pathwidth k and persistence l, and a graph that admits such a decomposition has bounded persistence pathwidth. We believe that this natural notion truly cap- tures the intuition behind the notion of pathwidth. We present some basic results regarding the gen- eral recognition of graphs having bounded persistence path decompositions.
Cite as: Downey, R.G. and McCartin, C. (2005). Bounded Persistence Pathwidth. In Proc. Eleventh Computing: The Australasian Theory Symposium (CATS2005), Newcastle, Australia. CRPIT, 41. Atkinson, M. and Dehne, F., Eds. ACS. 51-56.
pdf (from pdf (local if available) BibTeX EndNote GS