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

DOI10.1016/j.tcs.2010.06.017zbMath1231.05248OpenAlexW2090497853MaRDI 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

treewidthgraph algorithmsinterval graphslinear timeminimal triangulationpermutation graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

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

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

This page was built for publication: Treewidth and minimum fill-in on permutation graphs in linear time