Treewidth and minimum fill-in on permutation graphs in linear time
type: Item
instance of: scholarly article
title: Treewidth and minimum fill-in on permutation graphs in linear time
zbMATH Open document ID: 1231.05248
author: Daniel Meister
published in: Theoretical Computer Science
publication date: 2010-10-11T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5798140
zbMATH Keywords: graph algorithms
zbMATH Keywords: treewidth
zbMATH Keywords: minimal triangulation
zbMATH Keywords: linear time
zbMATH Keywords: permutation graphs
zbMATH Keywords: interval graphs
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.06.017
OpenAlex ID: W2090497853
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Treewidth and Pathwidth of Permutation Graphs
cites work: Treewidth and Minimum Fill-in on d-Trapezoid Graphs
cites work: The Pathwidth and Treewidth of Cographs
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Listing all potential maximal cliques of a graph
cites work: Optimal Linear Arrangement of Interval Graphs
cites work: Algorithmic graph theory and perfect graphs
cites work: Treewidth of cocomparability graphs and a new order-theoretic parameter
cites work: On treewidth and minimum fill-in of asteroidal triple-free graphs
cites work: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
cites work: Triangulating graphs without asteroidal triples
cites work: Characterizations and algorithmic applications of chordal graph embeddings
cites work: Q5588432
cites work: Triangulated graphs and the elimination process
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Computing the Minimum Fill-In is NP-Complete
DOI: 10.1016/J.TCS.2010.06.017
description: scientific article; zbMATH DE number 5798140