Fully Dynamic Matching in Bipartite Graphs

DOI10.1007/978-3-662-47672-7_14zbMath1372.68203arXiv1506.07076OpenAlexW853930207MaRDI QIDQ3448782

Aaron Bernstein, Clifford Stein

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.07076

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Round Compression for Parallel Matching Algorithms ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Shortest augmenting paths for online matchings on trees ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Shortest Augmenting Paths for Online Matchings on Trees ⋮ Approximating multistage matching problems ⋮ Unnamed Item ⋮ Improved algorithm for dynamic b-Matching ⋮ Improved Dynamic Graph Coloring ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Maintaining a large matching and a small vertex cover
• Linear-Time Approximation for Maximum Weight Matching
• Edge-Disjoint Spanning Trees of Finite Graphs
• AdWords and generalized online matching
• Online Stochastic Packing Applied to Display Ad Allocation
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Fully Dynamic Maximal Matching in O (log n) Update Time
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Distribution of a Product from Several Sources to Numerous Localities

This page was built for publication: Fully Dynamic Matching in Bipartite Graphs