Cover Image

New Separations and Reductions for Directed Preservers and Hopsets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hoppenworth, Gary, Xu, Yinzhan, Xu, Zixuan
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

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

Simple Linear-Size Additive Emulators
by: Hoppenworth, Gary
Published: (2023)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

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

Low Sensitivity Hopsets
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

Multiplicative Spanners in Minor-Free Graphs
by: Bodwin, Greg, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

A Unified Framework for Hopsets and Spanners
by: Neiman, Ofer, et al.
Published: (2021)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
by: Haeupler, Bernhard, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

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

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, 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)

Connectivity-Preserving Minimum Separator in AT-free Graphs
by: Kenig, Batya
Published: (2025)

Transitivity Preserving Projection in Directed Hypergraphs
by: Parsonage, Eric, et al.
Published: (2025)

Reviving Thorup's Shortcut Conjecture
by: Bernstein, Aaron, et al.
Published: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
by: Haeupler, Bernhard, et al.
Published: (2025)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication
by: Elkin, Michael, et al.
Published: (2025)

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

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

A New Approach for Approximating Directed Rooted Networks
by: Cohen, Sarel, et al.
Published: (2024)

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

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
by: Kenig, Batya
Published: (2025)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
by: Kurita, Kazuhiro, et al.
Published: (2025)

Optimal 4-Approximation for the Correlated Pandora's Problem
by: Bansal, Nikhil, et al.
Published: (2025)

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)