Maintaining a large matching and a small vertex cover

DOI10.1145/1806689.1806753MaRDI QIDQ2875173zbMATH OpenOpenAlexFDO

Authors Krzysztof Onak, Ronitt Rubinfeld

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1806689.1806753

zbMATH Keywords

data structuresdynamic algorithmsmaximum matchingvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Recommendations

• Covering graphs with matchings of fixed size
• scientific article; zbMATH DE number 2080241
• On approximating minimum vertex cover for graphs with perfect matching
• Computing and Combinatorics
• Cover a graph with small diameter by induced matchings
• Dynamic approximate vertex cover and maximum matching
• On matching cover of graphs
• On the parameterized vertex cover problem for graphs with perfect matching
• Covering cubic graphs with matchings of large size
• scientific article; zbMATH DE number 7399666

Cited in

(30)

• Dynamic algorithms via the primal-dual method
• Approximating dynamic weighted vertex cover with soft capacities
• Deterministic dynamic matching in \(O(1)\) update time
• Dynamic rank-maximal and popular matchings
• Fully dynamic matching in bipartite graphs
• Design of dynamic algorithms via primal-dual method
• Maintaining Near-Popular Matchings
• Deterministic fully dynamic data structures for vertex cover and matching
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Fully dynamic maximal matching in O( n) update time (corrected version)
• Dynamic approximate vertex cover and maximum matching
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
• An \(o(1)\)-approximation algorithm for dynamic weighted vertex cover with soft capacity
• Improved algorithm for dynamic b-matching
• Round compression for parallel matching algorithms
• Changing bases: multistage optimization for matroids and matchings
• Fully dynamic maximal matching in O( n) update time
• Dynamic Matching Algorithms in Practice
• Deterministic dynamic matching in worst-case update time
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• On regularity lemma and barriers in streaming and dynamic matching
• Fully dynamic sequential and distributed algorithms for MAX-CUT
• On solution discovery via reconfiguration
• Average sensitivity of the knapsack problem
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• A generalized matching reconfiguration problem
• Deterministic rounding of dynamic fractional matchings
• Dynamic algorithms for submodular matching

This page was built for publication: Maintaining a large matching and a small vertex cover

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