scientific article; zbMATH DE number 910887

MaRDI QIDQ4886061zbMATH OpenFDO

Authors D. Alberts, Monika R. Henzinger

Publication date 22 August 1996

zbMATH Keywords

bipartitenessconnectivitydynamic graph algorithmsmaximum cardinality matchingminimum spanning forestsrandom graphupdate operation

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)

Recommendations

• Average-case analysis of dynamic graph algorithms
• 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

(13)

• Average-case analysis of dynamic graph algorithms
• Average case analysis of dynamic geometric optimization
• Average case analysis of fully dynamic reachability for directed graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Convex transversals
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• scientific article; zbMATH DE number 2102755 (Why is no real title available?)
• Fully dynamic maximal matching in O( n) update time
• 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

This page was built for publication:

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