Copertina

Reviving Thorup's Shortcut Conjecture

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bernstein, Aaron, Fleischmann, Henry, Gutenberg, Maximilian Probst, Haeupler, Bernhard, Hoppenworth, Gary, Jiang, Yonggang, Li, George Z., Pettie, Seth, Saranurak, Thatchaphol, Schiller, Leon
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
di: Ashvinkumar, Vikrant, et al.
Pubblicazione: (2026)

DAG Projections: Reducing Distance and Flow Problems to DAGs
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
di: Long, Yaowei, et al.
Pubblicazione: (2024)

Space Complexity of Vertex Connectivity Oracles
di: Pettie, Seth, et al.
Pubblicazione: (2022)

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

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
di: Chen, Daoyuan, et al.
Pubblicazione: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Low-Step Multi-Commodity Flow Emulators
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2024)

Deterministic Almost-Linear-Time Gomory-Hu Trees
di: Abboud, Amir, et al.
Pubblicazione: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
di: Li, Xizhe, et al.
Pubblicazione: (2026)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
di: Jiang, Yonggang, et al.
Pubblicazione: (2025)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
di: Jiang, Yonggang, et al.
Pubblicazione: (2025)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
di: Adil, Deeksha, et al.
Pubblicazione: (2024)

Local Sherman's Algorithm for Multi-commodity Flow
di: Li, Jason, et al.
Pubblicazione: (2025)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
di: Gutenberg, Maximilian Probst, et al.
Pubblicazione: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
di: Sulser, Aurelio L., et al.
Pubblicazione: (2024)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Simple Linear-Size Additive Emulators
di: Hoppenworth, Gary
Pubblicazione: (2023)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
di: Kyng, Rasmus, et al.
Pubblicazione: (2025)

Expander Decomposition with Almost Optimal Overhead
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
di: Anand, Aditya, et al.
Pubblicazione: (2024)

An Approximation Algorithm for Graph Label Selection
di: John, Josia, et al.
Pubblicazione: (2026)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
di: Das, Debarati, et al.
Pubblicazione: (2026)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
di: He, Zhongtian, et al.
Pubblicazione: (2024)

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

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
di: Pettie, Seth, et al.
Pubblicazione: (2024)

Universal Perfect Samplers for Incremental Streams
di: Pettie, Seth, et al.
Pubblicazione: (2024)

Optimal Electrical Oblivious Routing on Expanders
di: Florescu, Cella, et al.
Pubblicazione: (2024)