Treewidth and pathwidth of permutation graphs

DOI10.1007/3-540-56939-1_66MaRDI QIDQ4630253zbMATH OpenOpenAlexFDO

Authors Ton Kloks, Dieter Kratsch, Hans L. Bodlaender

Publication date 29 March 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16657

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Treewidth and Pathwidth of Permutation Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Treewidth and minimum fill-in on permutation graphs in linear time
• Graph-Theoretic Concepts in Computer Science
• Computing the cutwidth of bipartite permutation graphs in linear time

Cites work

• Complexity of Finding Embeddings in a k-Tree
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 176761 (Why is no real title available?)
• scientific article; zbMATH DE number 176762 (Why is no real title available?)
• scientific article; zbMATH DE number 1301101 (Why is no real title available?)
• scientific article; zbMATH DE number 512817 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On Comparability and Permutation Graphs
• On the pathwidth of chordal graphs
• Permutation Graphs and Transitive Graphs
• Representation of a finite graph by a set of intervals on the real line
• The pathwidth and treewidth of cographs
• Topics on perfect graphs

Cited in

(9)

• Triangulating graphs without asteroidal triples
• Trivially-perfect width
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• The pathwidth and treewidth of cographs
• Graph-Theoretic Concepts in Computer Science
• Graph searching on chordal graphs
• Vertex ranking of asteroidal triple-free graphs
• The complexity of subgraph isomorphism for classes of partial k-trees

This page was built for publication: Treewidth and pathwidth of permutation graphs

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