Copertina

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Mehlhorn, Kurt, Nobahari, Romina
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
di: Ansaripour, Matin, et al.
Pubblicazione: (2024)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
di: Atalig, Sunny, et al.
Pubblicazione: (2025)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
di: Chuzhoy, Julia, et al.
Pubblicazione: (2024)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
di: Izumi, Taisuke, et al.
Pubblicazione: (2023)

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

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
di: Xu, Chao, et al.
Pubblicazione: (2026)

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

A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm
di: Abdulaziz, Mohammad, et al.
Pubblicazione: (2024)

Towards Fair Representation: Clustering and Consensus
di: Chakraborty, Diptarka, et al.
Pubblicazione: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

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

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving
di: Akrami, Hannaneh, et al.
Pubblicazione: (2026)

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

Improving Order with Queues
di: Karrenbauer, Andreas, et al.
Pubblicazione: (2022)

Semi-Robust Communication Complexity of Maximum Matching
di: Huete, Gabriel Cipriani, et al.
Pubblicazione: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
di: Rao, Satish
Pubblicazione: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
di: Kolmogorov, Vladimir
Pubblicazione: (2023)

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

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
di: Kurita, Kazuhiro, et al.
Pubblicazione: (2022)

The Communication Complexity of Pattern Matching with Edits Revisited
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2026)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
di: Saxena, Raghuvansh R., et al.
Pubblicazione: (2024)

Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
di: Hanaka, Tesshu, et al.
Pubblicazione: (2025)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
di: El-Hayek, Antoine, et al.
Pubblicazione: (2023)

Improved Approximation Algorithm for Maximum Balanced Biclique
di: Manurangsi, Pasin
Pubblicazione: (2026)

Max-Cut with Multiple Cardinality Constraints
di: Makarychev, Yury, et al.
Pubblicazione: (2025)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
di: Bodwin, Greg, et al.
Pubblicazione: (2023)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
di: Im, Sungjin, et al.
Pubblicazione: (2025)

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

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Efficient Parallel Algorithms for Hypergraph Matching
di: Reinstädtler, Henrik, et al.
Pubblicazione: (2026)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
di: Ahmadian, Sara, et al.
Pubblicazione: (2024)

Engineering Hypergraph $b$-Matching Algorithms
di: Großmann, Ernestine, et al.
Pubblicazione: (2024)

Algorithms for Parameterized String Matching with Mismatches
di: Saha, Apurba, et al.
Pubblicazione: (2024)

Semi-Streaming Algorithms for Hypergraph Matching
di: Reinstädtler, Henrik, et al.
Pubblicazione: (2025)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
di: Davies-Peck, Peter
Pubblicazione: (2026)

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

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
di: Papadopoulos, Kleitos
Pubblicazione: (2026)

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
di: Afshinmehr, Mahyar, et al.
Pubblicazione: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
di: Hwang, Samuel, et al.
Pubblicazione: (2024)