Bhattacharya, SayanSayanBhattacharyaGupta, ManojManojGuptaMohan, DivyarthiDivyarthiMohan2025-08-302025-08-302017-09-01[9783959770491]10.4230/LIPIcs.ESA.2017.152-s2.0-85030559537http://repository.iitgn.ac.in/handle/IITG2025/22403Recently 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<inf>v</inf>, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most b<inf>v</inf> edges incident on every node v. The maximum matching problem is a special case of this problem where b<inf>v</inf> = 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³ 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/ ϵ ⁴) update time. Thus, for every constant ϵ ∈ (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.falseDynamic data structures | Graph algorithmsConference Paper1 September 2017115cpConference Proceeding