Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
From MaRDI portal
Publication:442287
DOI10.1016/j.tcs.2012.05.002zbMath1246.68173MaRDI QIDQ442287
Publication date: 10 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.002
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
90C39: Dynamic programming
68P05: Data structures
Related Items
Cites Work
- Unnamed Item
- Fast minimal triangulation algorithm using minimum degree criterion
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- Existence of extensions and product extensions for discrete probability distributions
- A practical algorithm for making filled graphs minimal
- Maximum cardinality search for computing minimal triangulations of graphs
- Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Fast Computation of Minimal Fill Inside A Given Elimination Ordering
- Modification of the minimum-degree algorithm by multiple elimination
- The Evolution of the Minimum Degree Ordering Algorithm
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Fully dynamic algorithms for chordal graphs and split graphs
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- On Information and Sufficiency
- Graph-Theoretic Concepts in Computer Science
- A sufficiently fast algorithm for finding close to optimal clique trees
