Cover Image

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chuzhoy, Julia, Khanna, Sanjeev
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
by: Chuzhoy, Julia, et al.
Published: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
by: Assadi, Sepehr, et al.
Published: (2024)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
by: Chuzhoy, Julia, et al.
Published: (2025)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

Interval-Constrained Bipartite Matching over Time
by: Abels, Andreas, et al.
Published: (2024)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2024)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
by: Bernstein, Aaron, et al.
Published: (2024)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, et al.
Published: (2026)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
by: Soma, Tasuku, et al.
Published: (2025)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

New Algorithm for Combinatorial $n$-folds and Applications
by: Jansen, Klaus, et al.
Published: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
by: Agarwal, Arpit, et al.
Published: (2024)

Simpler O(1) Query Algorithm for Level Ancestors
by: Saxena, Sanjeev
Published: (2022)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

Optimal Rounding for Two-Stage Bipartite Matching
by: Pollner, Tristan, et al.
Published: (2025)

Stochastic Matching via In-n-Out Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2024)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

Approximate Bipartite $b$-Matching using Multiplicative Auction
by: Samineni, Bhargav, et al.
Published: (2024)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
by: Nägele, Martin, et al.
Published: (2026)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
by: Kuo, Tung-Wei
Published: (2024)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
by: Feng, Yilong, et al.
Published: (2025)

A New Impossibility Result for Online Bipartite Matching Problems
by: Chierichetti, Flavio, et al.
Published: (2025)