Cover Image

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Azarmehr, Amir, Behnezhad, Soheil, Roghani, Mohammad
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

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

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

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

Single-Pass Streaming CSPs via Two-Tier Sampling
by: Azarmehr, Amir, et al.
Published: (2026)

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Markov Chains with Rewinding
by: Azarmehr, Amir, et al.
Published: (2026)

Sublinear Algorithms for TSP via Path Covers
by: Behnezhad, Soheil, et al.
Published: (2023)

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

A Simple Analysis of Ranking in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

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

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Stochastic Matching via Local Sparsification
by: Ahmadian, Sara, et al.
Published: (2026)

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

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

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

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
by: Jin, Billy, et al.
Published: (2022)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
by: Bernstein, Aaron, et al.
Published: (2025)

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

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

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

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

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

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)

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

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

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
by: Björklund, Andreas, et al.
Published: (2023)