The pathwidth and treewidth of cographs

DOI10.1007/3-540-52846-6_99MaRDI QIDQ5056112zbMATH OpenOpenAlexWikidataFDO

Authors Rolf H. Möhring, Hans L. Bodlaender

Publication date 9 December 2022

Published in SWAT 90 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52846-6_99

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The Pathwidth and Treewidth of Cographs
• scientific article; zbMATH DE number 4173000
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Treewidth and pathwidth of permutation graphs
• scientific article; zbMATH DE number 176762

Cites work

• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Complexity of Finding Embeddings in a k-Tree
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 219268 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• scientific article; zbMATH DE number 4121438 (Why is no real title available?)
• Interval graphs and searching
• Searching and pebbling
• The vertex separation and search number of a graph

Cited in

(20)

• On the pathwidth of chordal graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Directed path-width and directed tree-width of directed co-graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Linear rank-width and linear clique-width of trees
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• Variable neighborhood search for the vertex separation problem
• On some simple widths
• Treewidth and pathwidth parameterized by the vertex cover number
• Mixed Search Number of Permutation Graphs
• Pathwidth of Circular-Arc Graphs
• Treewidth and pathwidth of permutation graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• Two strikes against perfect phylogeny
• Tree-decompositions of small pathwidth
• Reducing graph parameters by contractions and deletions
• Tree-width and path-width of comparability graphs of interval orders
• The micro-world of cographs

This page was built for publication: The pathwidth and treewidth of cographs

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