Tree-decompositions of small pathwidth

DOI10.1016/J.DAM.2004.01.012MaRDI QIDQ5916128zbMATH OpenOpenAlexFDO

Authors Jan Arne Telle

Publication date 22 February 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.01.012

zbMATH Keywords

graph algorithmmemory usagepathwidthtreewidth

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Review text

The treewidth \(\text{ tw}(G)\) of \(G\) can be defined as minimum width of a tree-decomposition of \(G\), or minimum \(\omega(H)-1\) of a chordal triangulation \(H\) of \(G\). Similarely, the pathwidth \(\text{ pw}(G)\) can be defined via path-decompositions or triangulations into interval graphs. Thereby a path-decomposition is a tree-decomposition \((T,X)\) where \(T\) is a path, and a chordal graph is interval if and only if it does not contain an asteroidal triple. A new parameter ``catwidth is introduced, either via tree-decompositions \((T,X)\) where \(T\) is a caterpillar (that is, \(\text{pw}(T) \leq 1\)), or via triangulations into so-called catval graphs. A chordal graph is catval if and only if it does not contain an extended asteroidal triple. We have \(\text{tw}(G) \leq \text{catw}(G) \leq \text{pw}(G)\) for all graphs \(G\). As for treewidth and pathwidth, the class of graphs with bounded catwidth is closed under minors, and, given \(G\) and \(k\), it is NP-complete to decide whether \(\text{catw}(G) \leq k\), even if \(G\) is the complement of a comparability graph.

Recommendations

• scientific article; zbMATH DE number 4173000
• Treewidth for graphs with small chordality
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• scientific article; zbMATH DE number 4210186
• The pathwidth and treewidth of cographs

Cites work

• All structured programs have small tree width and good register allocation
• Asteroidal Triple-Free Graphs
• Complexity of Finding Embeddings in a k-Tree
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 2086260 (Why is no real title available?)
• scientific article; zbMATH DE number 1222605 (Why is no real title available?)
• scientific article; zbMATH DE number 1303600 (Why is no real title available?)
• scientific article; zbMATH DE number 1756013 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 1926662 (Why is no real title available?)
• Memory requirements for table computations in partial k-tree algorithms
• Obstruction set isolation for the gate matrix layout problem
• Representation of a finite graph by a set of intervals on the real line
• The Pathwidth and Treewidth of Cographs
• The vertex separation and search number of a graph
• Triangulating graphs without asteroidal triples
• Triangulating multitolerance graphs

Cited in

(8)

• Induced separation dimension
• Characterizing width two for variants of treewidth
• scientific article; zbMATH DE number 4087704 (Why is no real title available?)
• Shortest path queries in digraphs of small treewidth
• scientific article; zbMATH DE number 1420905 (Why is no real title available?)
• A linear fixed parameter tractable algorithm for connected pathwidth
• Spined categories: generalizing tree-width beyond graphs
• The induced separation dimension of a graph

This page was built for publication: Tree-decompositions of small pathwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5916128)