2026-07-22T16:56:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4845 2024-03-06T10:35:25Z ddc:004 open_access

Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time Gupta, Manoj Graph Algorithm Dynamic Graph A sparse subgraph G' of G is called a matching sparsifier if the size or weight of matching in G' is approximately equal to the size or weight of maximum matching in G. Recently, algorithms have been developed to find matching sparsifiers in a static bipartite graph. In this paper, we show that we can find matching sparsifier even in an incremental bipartite graph. This observation leads to following results: 1. We design an algorithm that maintains a (1+epsilon) approximate matching in an incremental bipartite graph in O(log^2(n) / (epsilon^{4}) update time. 2. For weighted graphs, we design an algorithm that maintains (1+epsilon) approximate weighted matching in O((log(n)*log(n*N)) / (epsilon^4) update time where \maxweight is the maximum weight of any edge in the graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manoj Gupta 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.227 urn:nbn:de:0030-drops-48453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.227 eng https://creativecommons.org/licenses/by/3.0/legalcode