Treewidth of cocomparability graphs and a new order-theoretic parameter

DOI10.1007/BF01462229zbMath0811.06001OpenAlexW2016602672WikidataQ29543739 ScholiaQ29543739MaRDI QIDQ1337573

Rolf H. Möhring, Michel A. Habib

Publication date: 10 November 1994

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01462229

zbMATH Keywords

dimensionapproximation algorithmtreewidthinterval orderpathwidthcocomparability graphinterval width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Triangulating graphs without asteroidal triples ⋮ On treewidth and minimum fill-in of asteroidal triple-free graphs ⋮ Triangulating multitolerance graphs ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ A Characterisation of the Minimal Triangulations of Permutation Graphs ⋮ Tree-width and path-width of comparability graphs of interval orders ⋮ Counting linear extensions: parameterizations by treewidth ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Triangulating graphs with few \(P_4\)'s

Cites Work

• Interval dimension is a comparability invariant
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• On the pathwidth of chordal graphs
• Complexity of Finding Embeddings in a k-Tree
• On the Interplay Between Interval Dimension and Dimension
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Treewidth of cocomparability graphs and a new order-theoretic parameter