Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
type: Item
instance of: scholarly article
title: Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
zbMATH Open document ID: 1246.68173
author: Mauro Mezzini
published in: Theoretical Computer Science
publication date: 2012-08-10T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 6064621
zbMATH Keywords: chordal graphs
zbMATH Keywords: dynamic algorithms
zbMATH Keywords: minimal triangulations
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.05.002
OpenAlex ID: W311575298
cites work: A sufficiently fast algorithm for finding close to optimal clique trees
cites work: On the Desirability of Acyclic Database Schemes
cites work: Maximum cardinality search for computing minimal triangulations of graphs
cites work: A wide-range algorithm for minimal triangulation from an arbitrary ordering
cites work: Graph-Theoretic Concepts in Computer Science
cites work: A practical algorithm for making filled graphs minimal
cites work: Q4288578
cites work: On rigid circuit graphs
cites work: Degrees of acyclicity for hypergraphs and relational database schemes
cites work: The Evolution of the Minimum Degree Ordering Algorithm
cites work: Minimal triangulations of graphs: a survey
cites work: Fast Computation of Minimal Fill Inside A Given Elimination Ordering
cites work: Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
cites work: Fully dynamic algorithms for chordal graphs and split graphs
cites work: On Information and Sufficiency
cites work: Modification of the minimum-degree algorithm by multiple elimination
cites work: Existence of extensions and product extensions for discrete probability distributions
cites work: Fast minimal triangulation algorithm using minimum degree criterion
cites work: Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Computing the Minimum Fill-In is NP-Complete
DOI: 10.1016/J.TCS.2012.05.002
description: scientific article; zbMATH DE number 6064621