Semi-dynamic algorithms for strongly chordal graphs

DOI10.1142/S179383092150049XMaRDI QIDQ5013507zbMATH OpenFDO

Authors Md. Zamilur Rahman, Asish Mukhopadhyay

Publication date 30 November 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.07207

zbMATH Keywords

algorithm designgraph algorithmssemi-dynamic algorithmsstrongly chordal graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
• A fully dynamic algorithm for recognizing and representing chordal graphs
• scientific article; zbMATH DE number 1305520
• Algorithms and Computation
• Fully dynamic algorithms for chordal graphs and split graphs

Cites work

• Characterizations of strongly chordal graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
• Fully dynamic algorithms for chordal graphs and split graphs
• scientific article; zbMATH DE number 554762 (Why is no real title available?)

Cited in

(5)

• A uniform approach to semi-dynamic problems on digraphs
• Improved algorithms for weakly chordal graphs
• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide
• Semi-dynamic Algorithms for Strongly Chordal Graphs

This page was built for publication: Semi-dynamic algorithms for strongly chordal graphs

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