On treewidth and minimum fill-in of asteroidal triple-free graphs
From MaRDI portal
Publication:1392207
DOI10.1016/S0304-3975(96)00206-XzbMath0903.68139MaRDI QIDQ1392207
Dieter Kratsch, Ton Kloks, Jeremy P. Spinrad
Publication date: 23 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (27)
Minimal triangulations of graphs: a survey ⋮ An integer programming model for the Minimum Interval Graph Completion Problem ⋮ Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree ⋮ Edge Search Number of Cographs in Linear Time ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Independent sets in asteroidal triple-free graphs ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Mixed Search Number of Permutation Graphs ⋮ A Characterisation of the Minimal Triangulations of Permutation Graphs ⋮ Approximating the treewidth of AT-free graphs. ⋮ Computing hypergraph width measures exactly ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Searching for better fill-in ⋮ Efficiently enumerating minimal triangulations ⋮ Minimal split completions ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Characterizing and computing minimal cograph completions ⋮ On the complexity of computing treelength ⋮ Asteroidal triples of moplexes ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ On a property of minimal triangulations ⋮ GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH ⋮ Unnamed Item ⋮ Listing all potential maximal cliques of a graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Treewidth. Computations and approximations
- Triangulating graphs without asteroidal triples
- Triangulated graphs and the elimination process
- The Complexity of the Partial Order Dimension Problem
- On Comparability and Permutation Graphs
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- How to use the minimal separators of a graph for its chordal triangulation
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- Treewidth and Pathwidth of Permutation Graphs
- Approximating the bandwidth for asteroidal triple-free graphs
This page was built for publication: On treewidth and minimum fill-in of asteroidal triple-free graphs
