Image de couverture de livre

Covering Approximate Shortest Paths with DAGs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Assadi, Sepehr, Hoppenworth, Gary, Wein, Nicole
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Better Bounds for Semi-Streaming Single-Source Shortest Paths
par: Assadi, Sepehr, et autres
Publié: (2025)

The Discrepancy of Shortest Paths
par: Bodwin, Greg, et autres
Publié: (2024)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
par: Assadi, Sepehr
Publié: (2024)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
par: Chen, Kuowen, et autres
Publié: (2025)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
par: Bodwin, Greg, et autres
Publié: (2024)

Simple Linear-Size Additive Emulators
par: Hoppenworth, Gary
Publié: (2023)

Detecting Disjoint Shortest Paths in Linear Time and More
par: Akmal, Shyan, et autres
Publié: (2024)

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

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
par: Assadi, Sepehr, et autres
Publié: (2025)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
par: Assadi, Sepehr, et autres
Publié: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
par: Assadi, Sepehr, et autres
Publié: (2026)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
par: Bodwin, Greg, et autres
Publié: (2023)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
par: Assadi, Sepehr, et autres
Publié: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
par: Assadi, Sepehr, et autres
Publié: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
par: Carlson, Charlie, et autres
Publié: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
par: Górkiewicz, Adam, et autres
Publié: (2025)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
par: Assadi, Sepehr, et autres
Publié: (2023)

Multiplicative Spanners in Minor-Free Graphs
par: Bodwin, Greg, et autres
Publié: (2025)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
par: Hoppenworth, Gary, et autres
Publié: (2025)

New Separations and Reductions for Directed Preservers and Hopsets
par: Hoppenworth, Gary, et autres
Publié: (2024)

Improved Hardness-of-Approximation for Token Swapping
par: Hiken, Sam, et autres
Publié: (2024)

Improved 2-Approximate Shortest Paths for close vertex pairs
par: Gupta, Manoj
Publié: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
par: Dory, Michal, et autres
Publié: (2022)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
par: Ashvinkumar, Vikrant, et autres
Publié: (2024)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
par: Bentert, Matthias, et autres
Publié: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
par: Chitnis, Rajesh, et autres
Publié: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
par: Haeupler, Bernhard, et autres
Publié: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
par: Yan, Shuyi
Publié: (2025)

Coloring Graphs with Few Colors in the Streaming Model
par: Assadi, Sepehr, et autres
Publié: (2025)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
par: Assadi, Sepehr, et autres
Publié: (2022)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

Safe Sequences via Dominators in DAGs for Path-Covering Problems
par: Sena, Francisco, et autres
Publié: (2024)

Shortest Paths in Multimode Graphs
par: Kirkpatrick, Yael, et autres
Publié: (2025)

On Constrained and k Shortest Paths
par: Bendahi, Abderrahim, et autres
Publié: (2024)

All-Hops Shortest Paths
par: Williams, Virginia Vassilevska, et autres
Publié: (2024)

Improved Online Sorting
par: Nirjhor, Jubayer, et autres
Publié: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
par: Bernstein, Aaron, et autres
Publié: (2022)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
par: Makarychev, Yury, et autres
Publié: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
par: McCauley, Samuel, et autres
Publié: (2025)

The Steiner Shortest Path Tree Problem
par: Asher, Omer, et autres
Publié: (2025)