The Library
Improved algorithm for dynamic b-Matching
Tools
Bhattacharya, Sayan, Gupta, Manoj and Mohan, Divyarthi (2017) Improved algorithm for dynamic b-Matching. In: 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria, 4-6 Sep 2017. Published in: 25th Annual European Symposium on Algorithms (ESA 2017), 87 1:1-1:5. ISBN 9783959770491. doi:10.4230/LIPIcs.ESA.2017.1 ISSN 1868-8969.
|
PDF
WRAP-improved-algorithm-dynamic-b-Matching-Bhattacharya-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (822Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ESA.2017.1
Abstract
Recently there has been extensive work on maintaining (approximate)
maximum matchings in dynamic graphs. We consider a generalisation of
this problem known as the maximum b-matching: Every node v has a positive integral capacity bv, and the goal is to maintain an approximate) maximum cardinality subset of edges that contains at most bv edges incident on every node v. The maximum matching problem is a special case of this problem where bv = 1 for every node v.
Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum b-matching in a graph in O(log3 n) amortised update time. Their approximation ratio was a large (double digit) constant.
We significantly improve their result both in terms of approximation
ratio as well as update time. Specifically, we design a randomised dynamic algorithm that maintains a (2 + )-approximate maximum b-matching in expected amortised O(1= 4) update time. Thus, for every constant 2 (0; 1), we get expected amortised O(1) update time. Our algorithm generalises the framework of Baswana, Gupta, Sen [FOCS 2011] and Solomon [FOCS 2016] for maintaining a maximal matching in a dynamic graph.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Graph algorithms | ||||||
Journal or Publication Title: | 25th Annual European Symposium on Algorithms (ESA 2017) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
ISBN: | 9783959770491 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 1 September 2017 | ||||||
Dates: |
|
||||||
Volume: | 87 | ||||||
Page Range: | 1:1-1:5 | ||||||
DOI: | 10.4230/LIPIcs.ESA.2017.1 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 26 July 2017 | ||||||
Date of first compliant Open Access: | 26 July 2017 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 25th Annual European Symposium on Algorithms (ESA 2017) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Vienna, Austria | ||||||
Date(s) of Event: | 4-6 Sep 2017 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year