Cover Image

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ansaripour, Matin, Danaei, Alireza, Mehlhorn, Kurt
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

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

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

Improving Order with Queues
by: Karrenbauer, Andreas, et al.
Published: (2022)

Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms
by: Afshinmehr, Mahyar, et al.
Published: (2024)

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

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

Servicing Matched Client Pairs with Facilities
by: Abbasi, Fateme, et al.
Published: (2026)

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

Efficient Implementation of the Global Cardinality Constraint with Costs
by: Schmied, Margaux, et al.
Published: (2025)

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

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

A Note on Rounding Matchings in General Graphs
by: Dudeja, Aditi
Published: (2024)

On Thin Perfect Matchings up to Polylogarithmic Factors
by: Haqi, Alireza, et al.
Published: (2026)

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

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

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

Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
by: Castro, Lucas, et al.
Published: (2025)

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

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

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

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

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

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

Enhanced Graph Pattern Matching
by: Cotumaccio, Nicola
Published: (2024)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
by: Gomes, Guilherme C. M., et al.
Published: (2024)

Online Matching in Geometric Random Graphs
by: Sentenac, Flore, et al.
Published: (2023)

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

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
by: Gadekar, Ameet, et al.
Published: (2025)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Selection Improvements on the Parallel Iterative Algorithm for Stable Matching
by: Wynn, Scott, et al.
Published: (2024)

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
by: Liu, Yuxi, et al.
Published: (2023)

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
by: Dufay, Marc, et al.
Published: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

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

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

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

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
by: Derakhshan, Mahsa, et al.
Published: (2026)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
by: Koo, Jaehyun
Published: (2024)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
by: Behnezhad, Soheil, et al.
Published: (2024)