2026-07-23T15:54:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7844 2024-03-06T10:41:16Z ddc:004 open_access

Improved Algorithm for Dynamic b-Matching Bhattacharya, Sayan Gupta, Manoj Mohan, Divyarthi dynamic data structures graph algorithms 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 b_v, and the goal is to maintain an (approximate) maximum-cardinality 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 b-matching 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bhattacharya and Manoj Gupta and Divyarthi Mohan 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.15 urn:nbn:de:0030-drops-78443 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.15 eng https://creativecommons.org/licenses/by/3.0/legalcode