Treewidth of cocomparability graphs and a new order-theoretic parameter
type: Item
instance of: scholarly article
title: Treewidth of cocomparability graphs and a new order-theoretic parameter
zbMATH Open document ID: 0811.06001
DOI: 10.1007/BF01462229
author: Rolf H. Möhring
author: M. A. Habib
published in: Order
publication date: 1994-11-10T00:00:00Z
review text: The pathwidth of a cocomparability graph (AT-free graph) equals its treewidth. The proof is based on a new notation, called interval width, for a poset \(P\), which is the smallest width of an interval order contained in \(P\). Computing any of these parameters is NP-complete for cocomparability graphs of bipartite posets [\textit{S. Arnborg}, \textit{D. G. Corneil} and \textit{A. Proskurowski}, SIAM J. Algebraic Discrete Methods 8, 277-284 (1987; Zbl 0611.05022)], while polynomial time algorithms exist for cocomparability graphs of posets with bounded (interval) dimension [\textit{T. Kloks}, \textit{H. Bodlaender}, \textit{H. Müller} and \textit{D. Kratsch}, Lect. Notes Comput. Sci. 726, 260-271 (1993)].
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 683161
zbMATH Keywords: dimension
zbMATH Keywords: approximation algorithm
zbMATH Keywords: pathwidth
zbMATH Keywords: cocomparability graph
zbMATH Keywords: treewidth
zbMATH Keywords: interval width
zbMATH Keywords: interval order
Wikidata QID: Q29543739
MaRDI profile type: Publication
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Q4291429
cites work: Treewidth and Pathwidth of Permutation Graphs
cites work: The Pathwidth and Treewidth of Cographs
cites work: On the Interplay Between Interval Dimension and Dimension
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Q3328583
cites work: On the pathwidth of chordal graphs
cites work: Interval dimension is a comparability invariant
cites work: Q3964626
cites work: Q4246749
cites work: Q4918387
cites work: Q4734768
cites work: Q3197842
full work available at URL: https://doi.org/10.1007/bf01462229
OpenAlex ID: W2016602672
Recommended article: Tree-width and path-width of comparability graphs of interval orders
Recommended article: Q5702125
Recommended article: The Pathwidth and Treewidth of Cographs
Recommended article: The pathwidth and treewidth of cographs
Recommended article: Q4426346
Recommended article: Q4894618
Recommended article: Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
Recommended article: Tree-Related Widths of Graphs and Hypergraphs
Recommended article: Q3429490
Recommended article: A managed Bayesian risk approach for decision making alternatives
description: scientific article; zbMATH DE number 683161