A framework for dynamic matching in weighted graphs

DOI10.1145/3406325.3451113MaRDI QIDQ6087035zbMATH OpenOpenAlexFDO

Authors Aaron Bernstein, Aditi Dudeja, Zachary Langley

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

adaptive adversarydynamic algorithmsdynamic matchingmatching sparsifiersweighted matching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(13)

• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Deterministic dynamic matching in worst-case update time
• Fast primal-dual update against local weight update in linear assignment problem and its application
• Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
• On regularity lemma and barriers in streaming and dynamic matching
• Decremental matching in general weighted graphs
• A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
• Weighted matching in the random-order streaming and robust communication models
• Maximum weight b-matchings in random-order streams
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• Multiplicative auction algorithm for approximate maximum weight bipartite matching
• Dynamic algorithms for submodular matching

This page was built for publication: A framework for dynamic matching in weighted graphs

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