Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | Chang, Hsien-Chih, Conroy, Jonathan, Le, Hung, Solomon, Shay, Than, Cuong |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Ähnliche Einträge
Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
von: La, An, et al.
Veröffentlicht: (2025)
von: La, An, et al.
Veröffentlicht: (2025)
Tree-Like Shortcuttings of Trees
von: Le, Hung, et al.
Veröffentlicht: (2025)
von: Le, Hung, et al.
Veröffentlicht: (2025)
Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025)
von: Le, Hung, et al.
Veröffentlicht: (2025)
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
von: Le, Hung, et al.
Veröffentlicht: (2023)
von: Le, Hung, et al.
Veröffentlicht: (2023)
Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)
DAG Covers: The Steiner Point Effect
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)
Distance Approximating Minors for Planar and Minor-Free Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)
Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)
von: Solomon, Shay, et al.
Veröffentlicht: (2025)
Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)
von: Solomon, Shay, et al.
Veröffentlicht: (2023)
Towards Instance-Optimal Euclidean Spanners
von: Le, Hung, et al.
Veröffentlicht: (2024)
von: Le, Hung, et al.
Veröffentlicht: (2024)
A Lossless Deamortization for Dynamic Greedy Set Cover
von: Solomon, Shay, et al.
Veröffentlicht: (2024)
von: Solomon, Shay, et al.
Veröffentlicht: (2024)
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
von: Bukov, Anton, et al.
Veröffentlicht: (2023)
von: Bukov, Anton, et al.
Veröffentlicht: (2023)
Spanning and Metric Tree Covers Parameterized by Treewidth
von: Elkin, Michael, et al.
Veröffentlicht: (2025)
von: Elkin, Michael, et al.
Veröffentlicht: (2025)
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
von: Le, Hung, et al.
Veröffentlicht: (2021)
von: Le, Hung, et al.
Veröffentlicht: (2021)
Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)
Path-Reporting Distance Oracles for Vertex-Labeled Graphs
von: Neiman, Ofer, et al.
Veröffentlicht: (2026)
von: Neiman, Ofer, et al.
Veröffentlicht: (2026)
Dynamic Light Spanners in Doubling Metrics
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)
Optimal Euclidean Tree Covers
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)
Path-Reporting Distance Oracles with Linear Size
von: Neiman, Ofer, et al.
Veröffentlicht: (2024)
von: Neiman, Ofer, et al.
Veröffentlicht: (2024)
Hamming Distance Oracle
von: Boneh, Itai, et al.
Veröffentlicht: (2024)
von: Boneh, Itai, et al.
Veröffentlicht: (2024)
Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
von: Kokai, Toranosuke, et al.
Veröffentlicht: (2025)
von: Kokai, Toranosuke, et al.
Veröffentlicht: (2025)
Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)
von: Boneh, Itai, et al.
Veröffentlicht: (2025)
Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)
How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
von: Conroy, Jonathan, et al.
Veröffentlicht: (2025)
von: Conroy, Jonathan, et al.
Veröffentlicht: (2025)
O(1)-Distortion Planar Emulators for String Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)
Simpler and Improved Replacement Path Coverings
von: Bilò, Davide, et al.
Veröffentlicht: (2026)
von: Bilò, Davide, et al.
Veröffentlicht: (2026)
Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)
Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)
Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
von: Browne, Reilly, et al.
Veröffentlicht: (2026)
von: Browne, Reilly, et al.
Veröffentlicht: (2026)
Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)
von: Peng, Pan, et al.
Veröffentlicht: (2026)
Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)
Max Cut with Small-Dimensional SDP Solutions
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2026)
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2026)
New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
von: Ding, Xiangyun, et al.
Veröffentlicht: (2025)
von: Ding, Xiangyun, et al.
Veröffentlicht: (2025)
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
von: Elkin, Michael, et al.
Veröffentlicht: (2023)
von: Elkin, Michael, et al.
Veröffentlicht: (2023)
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)
Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
von: Karamchedu, Mithra, et al.
Veröffentlicht: (2025)
von: Karamchedu, Mithra, et al.
Veröffentlicht: (2025)
A Separator for Minor-Free Graphs Beyond the Flow Barrier
von: Le, Hung
Veröffentlicht: (2026)
von: Le, Hung
Veröffentlicht: (2026)
Ähnliche Einträge
-
Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
von: La, An, et al.
Veröffentlicht: (2025) -
Tree-Like Shortcuttings of Trees
von: Le, Hung, et al.
Veröffentlicht: (2025) -
Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025) -
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
von: Le, Hung, et al.
Veröffentlicht: (2023) -
Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)