Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n^2) update-time

DOI10.1016/J.TCS.2012.05.002MaRDI QIDQ442287zbMATH OpenOpenAlexFDO

Authors Mauro Mezzini

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

zbMATH Keywords

chordal graphsdynamic algorithmsminimal triangulations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1305520
• Fully dynamic algorithms for chordal graphs and split graphs
• Maintaining chordal graphs dynamically: improved upper and lower bounds
• Algorithms and Computation
• A fully dynamic algorithm for recognizing and representing chordal graphs

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• A practical algorithm for making filled graphs minimal
• A sufficiently fast algorithm for finding close to optimal clique trees
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Computing the Minimum Fill-In is NP-Complete
• Degrees of acyclicity for hypergraphs and relational database schemes
• Existence of extensions and product extensions for discrete probability distributions
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• Fast minimal triangulation algorithm using minimum degree criterion
• Fully dynamic algorithms for chordal graphs and split graphs
• Graph-Theoretic Concepts in Computer Science
• Maximum cardinality search for computing minimal triangulations of graphs
• Minimal triangulations of graphs: a survey
• Modification of the minimum-degree algorithm by multiple elimination
• On Information and Sufficiency
• On rigid circuit 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
• Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
• The Evolution of the Minimum Degree Ordering Algorithm

Cited in

(8)

• Maintaining chordal graphs dynamically: improved upper and lower bounds
• Fully dynamic algorithms for chordal graphs and split graphs
• Maintaining graph properties of weakly chordal graphs
• On the theory of dynamic graph regression problem
• Semi-dynamic algorithms for strongly chordal graphs
• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• Algorithms and Computation
• A fully dynamic algorithm for recognizing and representing chordal graphs

This page was built for publication: Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442287)