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

DOI10.1016/J.TCS.2012.05.002zbMATH Open1246.68173OpenAlexW311575298MaRDI QIDQ442287FDOQ442287

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

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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• A fully dynamic algorithm for recognizing and representing chordal graphs
• Maintaining graph properties of weakly chordal graphs
• Algorithms and Computation
• Semi-dynamic algorithms for strongly 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)