Image de couverture de livre

Shortcuts and Transitive-Closure Spanners Approximation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chalermsook, Parinya, Jiang, Yonggang, Mukhopadhyay, Sagnik, Nanongkai, Danupon
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

Minimum $s$--$t$ Cuts with Fewer Cut Queries
par: Jiang, Yonggang, et autres
Publié: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
par: Bernstein, Aaron, et autres
Publié: (2022)

Hardness and Approximation for Coloring Digraphs
par: Chalermsook, Parinya, et autres
Publié: (2026)

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
par: Chalermsook, Parinya, et autres
Publié: (2025)

A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
par: Chalermsook, Parinya, et autres
Publié: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
par: Chalermsook, Parinya, et autres
Publié: (2021)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
par: Fischer, Olivier, et autres
Publié: (2025)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
par: Blikstad, Joakim, et autres
Publié: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
par: Goranci, Gramoz, et autres
Publié: (2023)

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
par: Herold, Martin G., et autres
Publié: (2025)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
par: Haeupler, Bernhard, et autres
Publié: (2025)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
par: Ashvinkumar, Vikrant, et autres
Publié: (2023)

Approximate Light Spanners in Planar Graphs
par: Le, Hung, et autres
Publié: (2025)

Reviving Thorup's Shortcut Conjecture
par: Bernstein, Aaron, et autres
Publié: (2025)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
par: Abbasi, Fateme, et autres
Publié: (2023)

Routing-Controlled Spanners
par: Grigorescu, Elena, et autres
Publié: (2024)

Directed Buy-at-Bulk Spanners
par: Grigorescu, Elena, et autres
Publié: (2024)

New Greedy Spanners and Applications
par: Popova, Elizaveta, et autres
Publié: (2026)

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

Minimum Temporal Spanners in Happy Graphs
par: Casteigts, Arnaud, et autres
Publié: (2026)

Almost-Optimal Sublinear Additive Spanners
par: Tan, Zihan, et autres
Publié: (2023)

Graph Spanners for Group Steiner Distances
par: Bilò, Davide, et autres
Publié: (2024)

A Unified Framework for Hopsets and Spanners
par: Neiman, Ofer, et autres
Publié: (2021)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
par: Jiang, Yonggang, et autres
Publié: (2025)

Parameterized Linear Time Transitive Closure
par: Kritikakis, Giorgos, et autres
Publié: (2024)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
par: Ghaffari, Mohsen, et autres
Publié: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
par: He, Jialin, et autres
Publié: (2025)

A Simple Dynamic Spanner via APSP
par: Kyng, Rasmus, et autres
Publié: (2024)

Greedy Completion for Weighted $(α,β)$-Spanners
par: Tzalik, Elad
Publié: (2026)

Lightweight Near-Additive Spanners
par: Gitlitz, Yuval, et autres
Publié: (2024)

Fine-Grained Complexity of Continuous Euclidean k-Center
par: Blank, Lotte, et autres
Publié: (2026)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
par: Qi, Chuhan
Publié: (2025)

A Lower Bound for Light Spanners in General Graphs
par: Bodwin, Greg, et autres
Publié: (2024)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
par: Ahmed, Reyan, et autres
Publié: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
par: Haeupler, Bernhard, et autres
Publié: (2025)

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

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
par: Parter, Merav, et autres
Publié: (2024)

The Complexity of Geodesic Spanners
par: de Berg, Sarita, et autres
Publié: (2023)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
par: Bhore, Sujoy, et autres
Publié: (2024)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
par: Jiang, Yonggang, et autres
Publié: (2025)