Fully dynamic algorithms for chordal graphs and split graphs

DOI10.1145/1383369.1383371zbMath1445.05103OpenAlexW2055371600MaRDI QIDQ4962745

Louis Ibarra

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1383369.1383371

zbMATH Keywords

chordal graphssplit graphsclique treesdynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time ⋮ Fully dynamic representations of interval graphs ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Two methods for the generation of chordal graphs ⋮ Recognition of split-graphic sequences ⋮ Minimal split completions ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network ⋮ Maximal sub-triangulation in pre-processing phylogenetic data ⋮ Unnamed Item ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ Efficient local updates for undirected graphical models ⋮ Dynamically maintaining split graphs ⋮ Semi-dynamic algorithms for strongly chordal graphs ⋮ Fully dynamic recognition of proper circular-arc graphs