Buchumschlag

Streaming Maximal Matching with Bounded Deletions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Khanna, Sanjeev, Konrad, Christian, Dark, Jacques
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

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

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions
von: Zhao, Fuheng, et al.
Veröffentlicht: (2023)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Adversarial Robustness on Insertion-Deletion Streams
von: Gribelyuk, Elena, et al.
Veröffentlicht: (2026)

Constructing Long Paths in Graph Streams
von: Konrad, Christian, et al.
Veröffentlicht: (2025)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

On the Parallel Complexity of Finding a Matroid Basis
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Query Complexity of the Metric Steiner Tree Problem
von: Chen, Yu, et al.
Veröffentlicht: (2022)

Semi-Streaming Algorithms for Hypergraph Matching
von: Reinstädtler, Henrik, et al.
Veröffentlicht: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
von: Wlodarczyk, Michal
Veröffentlicht: (2023)

Deletion Robust Submodular Maximization over Matroids
von: Dütting, Paul, et al.
Veröffentlicht: (2022)

Grouped Color Deletion, Lasserre Exactness and Clique-Sum Locality for Rainbow Matching
von: Stamoulis, Georgios
Veröffentlicht: (2026)

Maximizing Weighted Dominance in the Plane
von: Akram, Waseem, et al.
Veröffentlicht: (2024)

Semi-Robust Communication Complexity of Maximum Matching
von: Huete, Gabriel Cipriani, et al.
Veröffentlicht: (2025)

Unit Interval Selection in Random Order Streams
von: Alexandru, Cezar-Mihail, et al.
Veröffentlicht: (2026)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Deletion Robust Non-Monotone Submodular Maximization over Matroids
von: Dütting, Paul, et al.
Veröffentlicht: (2022)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
von: Buchbinder, Niv, et al.
Veröffentlicht: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
von: Ferdous, S M, et al.
Veröffentlicht: (2023)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

How to Find Long Maximal Exact Matches and Ignore Short Ones
von: Gagie, Travis
Veröffentlicht: (2024)

Almost Tight Bounds for Online Hypergraph Matching
von: Tröbst, Thorben, et al.
Veröffentlicht: (2024)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
von: Hashemi, Diba, et al.
Veröffentlicht: (2024)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Pathfinding in Self-Deleting Graphs
von: Dvořák, Michal, et al.
Veröffentlicht: (2025)