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

DOI10.1016/J.TCS.2010.06.017zbMATH Open1231.05248OpenAlexW2090497853MaRDI QIDQ708222FDOQ708222

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

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

zbMATH Keywords

treewidthgraph algorithmsinterval graphspermutation graphslinear timeminimal triangulation

Mathematics Subject Classification ID

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

Cites Work

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

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)