Treewidth and minimum fill-in on permutation graphs in linear time

DOI10.1016/j.tcs.2010.06.017zbMath1231.05248MaRDI QIDQ708222

Daniel Meister

Publication date: 11 October 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.017

zbMATH Keywords

treewidth; graph algorithms; interval graphs; linear time; minimal triangulation; permutation graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Faster and enhanced inclusion-minimal cograph completion, Two characterisations of the minimal triangulations of permutation graphs, Permutation bigraphs and interval containments, Restricted vertex multicut on permutation graphs

Cites Work

• Unnamed Item
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Listing all potential maximal cliques of a graph
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Algorithmic graph theory and perfect graphs
• Triangulating graphs without asteroidal triples
• Triangulated graphs and the elimination process
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• Optimal Linear Arrangement of Interval Graphs