A practical algorithm for making filled graphs minimal
From MaRDI portal
Publication:1589427
DOI10.1016/S0304-3975(99)00126-7zbMath0952.68104OpenAlexW1966454892WikidataQ127124540 ScholiaQ127124540MaRDI QIDQ1589427
Jean R. S. Blair, Jan Arne Telle, Pinar Heggernes
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00126-7
Related Items (19)
Minimal triangulations of graphs: a survey ⋮ A vertex incremental approach for maintaining chordality ⋮ Safe separators for treewidth ⋮ Lex M versus MCS-M ⋮ Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree ⋮ The tree-width of C ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time ⋮ Efficiently enumerating minimal triangulations ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Treewidth computations. I: Upper bounds ⋮ Minimal split completions ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Characterizing and computing minimal cograph completions ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
Uses Software
Cites Work
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Chordal completions of planar graphs
- On the Desirability of Acyclic Database Schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
- Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
- Sparse matrix test problems
- A Linear Reordering Algorithm for Parallel Pivoting of Chordal Graphs
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Making an arbitrary filled graph minimal by removing fill edges
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A practical algorithm for making filled graphs minimal
