Treewidth of cocomparability graphs and a new order-theoretic parameter (Q1337573): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 02:58, 5 March 2024

scientific article
Language Label Description Also known as
English
Treewidth of cocomparability graphs and a new order-theoretic parameter
scientific article

    Statements

    Treewidth of cocomparability graphs and a new order-theoretic parameter (English)
    0 references
    0 references
    0 references
    0 references
    10 November 1994
    0 references
    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)].
    0 references
    dimension
    0 references
    approximation algorithm
    0 references
    pathwidth
    0 references
    cocomparability graph
    0 references
    treewidth
    0 references
    interval width
    0 references
    interval order
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references