Cover Image

Faster Semi-streaming Matchings via Alternating Trees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mitrović, Slobodan, Mukherjee, Anish, Sankowski, Piotr, Sheu, Wen-Horng
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 framework for boosting matching approximation: parallel, distributed, and dynamic
by: Mitrović, Slobodan, et al.
Published: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

Dynamic Construction of the Lovász Local Lemma
by: Haeupler, Bernhard, et al.
Published: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Modeling Online Paging in Multi-Core Systems
by: Mari, Mathieu, et al.
Published: (2024)

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)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Locally computing edge orientations
by: Mitrović, Slobodan, et al.
Published: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
by: Dhulipala, Laxman, et al.
Published: (2024)

Online Multi-level Aggregation with Delays and Stochastic Arrivals
by: Mari, Mathieu, et al.
Published: (2024)

Online matching with delays and stochastic arrival times
by: Mari, Mathieu, et al.
Published: (2022)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)

Engineering Semi-streaming DFS algorithms
by: Bhagavan, Kancharla Nikhilesh, et al.
Published: (2024)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

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

Differentially Private Gomory-Hu Trees
by: Aamand, Anders, et al.
Published: (2024)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

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

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

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

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

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

Faster PBWT prefix-array access via batching
by: Gagie, Travis
Published: (2026)

Entropy Regularization and Faster Decremental Matching in General Graphs
by: Chen, Jiale, et al.
Published: (2023)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
by: Tian, Kangyi, et al.
Published: (2026)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)

Faster optimal univariate microgaggregation
by: Stamm, Felix I., et al.
Published: (2024)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)