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

DOI10.1016/J.TCS.2010.06.017MaRDI QIDQ708222zbMATH OpenOpenAlexFDO

Authors 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 graphspermutation graphslinear timeminimal triangulation

Mathematics Subject Classification ID

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

Recommendations

• Graph-Theoretic Concepts in Computer Science
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• A Characterisation of the Minimal Triangulations of Permutation Graphs
• Two characterisations of the minimal triangulations of permutation graphs

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Listing all potential maximal cliques of a graph
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Optimal Linear Arrangement of Interval Graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Triangulated graphs and the elimination process
• Triangulating graphs without asteroidal triples

Cited in

(8)

• A Characterisation of the Minimal Triangulations of Permutation Graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Treewidth and Pathwidth of Permutation Graphs
• Restricted vertex multicut on permutation graphs
• Permutation bigraphs and interval containments
• Treewidth and pathwidth of permutation graphs
• Graph-Theoretic Concepts in Computer Science
• Two characterisations of the minimal triangulations of permutation graphs

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

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