Treewidth and pathwidth of permutation graphs

DOI10.1007/3-540-56939-1_66zbMath1418.68162OpenAlexW1491170911MaRDI QIDQ4630253

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

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

Related Items

Triangulating graphs without asteroidal triples, The complexity of subgraph isomorphism for classes of partial k-trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Topics on perfect graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the pathwidth of chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• On Comparability and Permutation Graphs
• Complexity of Finding Embeddings in a k-Tree
• The pathwidth and treewidth of cographs
• Permutation Graphs and Transitive Graphs