Litcius/Paper detail

Dynamic Algorithms for Maximum Matching Size

Soheil Behnezhad

2023Society for Industrial and Applied Mathematics eBooks14 citationsDOI

Abstract

We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. For instance, it is known how to maintain a 1/2-approximate matching in (poly log n) update time or a 2/3-approximate match­ing in update time, where n is the number of vertices. It has been a long-standing open problem to determine whether either of these bounds can be improved.

Topics & Concepts

Bipartite graphMatching (statistics)Approximation algorithmMathematicsCharacterization (materials science)Sublinear functionAlgorithmCombinatoricsBlossom algorithmSet (abstract data type)Discrete mathematicsGraphComputer scienceNanotechnologyProgramming languageMaterials scienceStatisticsComplexity and Algorithms in GraphsAdvanced Graph Theory ResearchOptimization and Search Problems
Dynamic Algorithms for Maximum Matching Size | Litcius