Cover Image

Semi-Robust Communication Complexity of Maximum Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Huete, Gabriel Cipriani, Diddapur, Adithya, Dvořák, Pavel, Konrad, Christian
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Unit Interval Selection in Random Order Streams
by: Alexandru, Cezar-Mihail, et al.
Published: (2026)

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

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

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

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
by: Fischer, Manuela, et al.
Published: (2021)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

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

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

Weighted Matching in the Random-Order Streaming and Robust Communication Models
by: Hashemi, Diba, et al.
Published: (2024)

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

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

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

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

Faster Semi-streaming Matchings via Alternating Trees
by: Mitrović, Slobodan, et al.
Published: (2024)

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

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

On the Communication Complexity of Approximate Pattern Matching
by: Kociumaka, Tomasz, et al.
Published: (2024)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
by: Arkhipov, Pavel, et al.
Published: (2026)

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

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

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

On the Advice Complexity of Online Matching on the Line
by: Csaba, Béla, et al.
Published: (2024)

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

Constructing Long Paths in Graph Streams
by: Konrad, Christian, et al.
Published: (2025)

Pattern Matching with Mismatches and Wildcards
by: Bathie, Gabriel, et al.
Published: (2024)

Weighted $k$-Server Admits an Exponentially Competitive Algorithm
by: Bijoy, Adithya, et al.
Published: (2025)

Interval Selection in Sliding Windows
by: Alexandru, Cezar-Mihail, et al.
Published: (2024)

Parameterized Complexity of Scheduling Problems in Robotic Process Automation
by: Dvořák, Michal, et al.
Published: (2026)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

Internal Pattern Matching in Small Space and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

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

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

Graph Reconstruction via MIS Queries
by: Konrad, Christian, et al.
Published: (2024)

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

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

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Complexity and Algorithm for the Matching vertex-cutset Problem
by: Li, Hengzhe, et al.
Published: (2025)