Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
From MaRDI portal
Publication:5252659
DOI10.1137/130914140zbMath1314.05155OpenAlexW2178621981MaRDI QIDQ5252659
Surender Baswana, Manoj Gupta, Sandeep Sen
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/130914140
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (13)
Deterministic dynamic matching in worst-case update time ⋮ Dynamic rank-maximal and popular matchings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic clustering to minimize the sum of radii ⋮ Dynamic Matching Algorithms in Practice ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Dynamic graph coloring ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Unnamed Item ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Approximating dynamic weighted vertex cover with soft capacities
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fully-dynamic min-cut
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Matching theory
- Maintaining a large matching and a small vertex cover
- Towards polynomial lower bounds for dynamic problems
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Fully dynamic randomized algorithms for graph spanners
- Popular Matchings
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
- Faster scaling algorithms for general graph matching problems
- Sparsification—a technique for speeding up dynamic graph algorithms
- Cuckoo hashing
- Matching, Euler tours and the Chinese postman
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Paths, Trees, and Flowers
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Dynamic graph connectivity in polylogarithmic worst case time
- College Admissions and the Stability of Marriage
This page was built for publication: Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
