Treewidth of cocomparability graphs and a new order-theoretic parameter
From MaRDI portal
Publication:1337573
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
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
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
