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