Buchumschlag

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chang, Hsien-Chih, Conroy, Jonathan, Le, Hung, Solomon, Shay, Than, Cuong
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
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)

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)

DAG Covers: The Steiner Point Effect
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)

Dynamic Set Cover with Worst-Case Recourse
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)

Towards Instance-Optimal Euclidean Spanners
von: Le, Hung, et al.
Veröffentlicht: (2024)

A Lossless Deamortization for Dynamic Greedy Set Cover
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)

Spanning and Metric Tree Covers Parameterized by Treewidth
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)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
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)

Dynamic Light Spanners in Doubling Metrics
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

Optimal Euclidean Tree Covers
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Path-Reporting Distance Oracles with Linear Size
von: Neiman, Ofer, et al.
Veröffentlicht: (2024)

Hamming Distance Oracle
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)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Sublinear Algorithms for TSP via Path Covers
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)

O(1)-Distortion Planar Emulators for String Graphs
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)

Simpler and Improved Replacement Path Coverings
von: Bilò, Davide, et al.
Veröffentlicht: (2026)

Covering Approximate Shortest Paths with DAGs
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)

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
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)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Max Cut with Small-Dimensional SDP Solutions
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)

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
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)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
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)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
von: Karamchedu, Mithra, et al.
Veröffentlicht: (2025)

A Separator for Minor-Free Graphs Beyond the Flow Barrier
von: Le, Hung
Veröffentlicht: (2026)