A vertex incremental approach for maintaining chordality
From MaRDI portal
Publication:819824
DOI10.1016/J.DISC.2005.12.002zbMath1087.05054OpenAlexW2064246684MaRDI QIDQ819824
Pinar Heggernes, Anne Berry, Yngve Villanger
Publication date: 29 March 2006
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.002
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (14)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ An introduction to clique minimal separator decomposition ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Computing and listing avoidable vertices and paths ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Computing and listing avoidable vertices and paths ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ Minimal comparability completions of arbitrary graphs ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Treewidth computations. I: Upper bounds ⋮ Characterizing and computing minimal cograph completions ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Dynamically maintaining split graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
- Maximal chordal subgraphs
- Counting clique trees and computing perfect elimination schemes in parallel
- A chordal preconditioner for large-scale optimization
- A practical algorithm for making filled graphs minimal
- An efficient algorithm for finding a two-pair, and its applications
- Optimizing weakly triangulated graphs
- A characterisation of rigid circuit graphs
- Maximum cardinality search for computing minimal triangulations of graphs
- Algorithms for weakly triangulated graphs
- Incidence matrices and interval graphs
- Maximal sub-triangulation in pre-processing phylogenetic data
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Desirability of Acyclic Database Schemes
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
- The Pathwidth and Treewidth of Cographs
- Generating weakly triangulated graphs
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Complexity classification of some edge modification problems
This page was built for publication: A vertex incremental approach for maintaining chordality
