Randomized fully dynamic graph algorithms with polylogarithmic time per operation
From MaRDI portal
Recommendations
Cited in
(58)- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Fully-dynamic MIN-cut
- scientific article; zbMATH DE number 7561709 (Why is no real title available?)
- Upper and lower bounds for fully retroactive graph problems
- Near-optimal fully-dynamic graph connectivity
- Dynamic connectivity for axis-parallel rectangles
- Maintaining dynamic minimum spanning trees: an experimental study
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- The randomized complexity of maintaining the minimum
- A survey on combinatorial optimization in dynamic environments
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- scientific article; zbMATH DE number 2102755 (Why is no real title available?)
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Discovering recurring activity in temporal networks
- scientific article; zbMATH DE number 7651141 (Why is no real title available?)
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
- Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs
- Dynamic approximate vertex cover and maximum matching
- Good r-divisions imply optimal amortized decremental biconnectivity
- Deterministic fault-tolerant connectivity labeling scheme
- Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
- Fully dynamic all pairs shortest paths with real edge weights
- Fully dynamic biconnectivity in graphs
- An improved algorithm for incremental DFS tree in undirected graphs
- Almost optimal exact distance oracles for planar graphs
- A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
- Time windowed data structures for graphs
- The saga of minimum spanning trees
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- Fully dynamic sequential and distributed algorithms for MAX-CUT
- Fully-adaptive dynamic connectivity of square intersection graphs
- Maintaining minimum spanning forests in dynamic graphs
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Kinetic geodesic Voronoi diagrams in a simple polygon
- Randomization for efficient dynamic graph algorithms (invited talk)
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- scientific article; zbMATH DE number 1775391 (Why is no real title available?)
- Constant-time dynamic weight approximation for minimum spanning forest
- Local update algorithms for random graphs
- Faster Fully-Dynamic Minimum Spanning Forest
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- LS(graph): a constraint-based local search for constraint optimization on trees and paths
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Fully dynamic maximal matching in O( n) update time
- Dynamic geometric connectivity in the plane with constant query time
- Optimal decremental connectivity in planar graphs
- Maintaining minimum spanning trees in dynamic graphs
- A consistent semantics of self-adjusting computation
- Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
- Decremental Dynamic Connectivity
- Algorithmic techniques for maintaining shortest routes in dynamic networks
- Incremental dead state detection in logarithmic time
- Dynamic graph connectivity in polylogarithmic worst case time
- Fully dynamic randomized algorithms for graph spanners
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
- Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
- Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
- scientific article; zbMATH DE number 910887 (Why is no real title available?)
This page was built for publication: Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158547)
