The pathwidth and treewidth of cographs

DOI10.1007/3-540-52846-6_99zbMath1502.05232OpenAlexW1557930107WikidataQ59568079 ScholiaQ59568079MaRDI QIDQ5056112

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) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Variable neighborhood search for the vertex separation problem, Reducing graph parameters by contractions and deletions, Mixed Search Number of Permutation Graphs, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Treewidth and pathwidth of permutation graphs, Two strikes against perfect phylogeny, On the pathwidth of chordal graphs, Linear rank-width and linear clique-width of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Complement reducible graphs
• The vertex separation and search number of a graph
• Searching and pebbling
• Graph minors. XIII: The disjoint paths problem
• A Linear Recognition Algorithm for Cographs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree