Bhattacharya, Sayan ;
Gupta, Manoj ;
Mohan, Divyarthi
Improved Algorithm for Dynamic bMatching
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 bmatching: Every node v has a positive integral capacity b_v, and the goal is to maintain an (approximate) maximumcardinality subset of edges that contains at most b_v edges incident on every node v. The maximum matching problem is a special case of this problem where b_v = 1 for every node v.
Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum bmatching in a graph in O(log^3 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+epsilon)approximate maximum $b$matching in expected amortised O(1/epsilon^4) update time. Thus, for every constant epsilon in (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.
BibTeX  Entry
@InProceedings{bhattacharya_et_al:LIPIcs:2017:7844,
author = {Sayan Bhattacharya and Manoj Gupta and Divyarthi Mohan},
title = {{Improved Algorithm for Dynamic bMatching}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {15:115:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7844},
URN = {urn:nbn:de:0030drops78443},
doi = {10.4230/LIPIcs.ESA.2017.15},
annote = {Keywords: dynamic data structures, graph algorithms}
}
2017
Keywords: 

dynamic data structures, graph algorithms 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

2017 