Average-case analysis of dynamic graph algorithms

DOI10.1007/PL00009186MaRDI QIDQ1386353zbMATH OpenOpenAlexFDO

Authors D. Alberts, Monika R. Henzinger

Publication date 8 September 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009186

zbMATH Keywords

dynamic graph algorithmsmaximum cardinality matchingminimum spanning forest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 910887
• scientific article; zbMATH DE number 1263228
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• Fully dynamic maximal matching in O( n) update time

Cited in

(11)

• Average case analysis of fully dynamic reachability for directed graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 2102755 (Why is no real title available?)
• scientific article; zbMATH DE number 910887 (Why is no real title available?)
• The State of the Art in Dynamic Graph Algorithms
• Local update algorithms for random graphs
• Average Sensitivity of Graph Algorithms
• Average case analysis of fully dynamic connectivity for directed graphs
• Average-case analysis of best-first search in two representative directed acyclic graphs
• Maintaining dynamic minimum spanning trees: an experimental study

This page was built for publication: Average-case analysis of dynamic graph algorithms

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