Buchumschlag

Approximate Light Spanners in Planar Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Le, Hung, Solomon, Shay, Than, Cuong, Tóth, Csaba D., Zhang, Tianyi
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

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

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
von: La, An, 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)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Tree-Like Shortcuttings of Trees
von: Le, Hung, 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)

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
von: Le, Hung, et al.
Veröffentlicht: (2021)

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)

Almost-Optimal Sublinear Additive Spanners
von: Tan, Zihan, et al.
Veröffentlicht: (2023)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)

Distances in Planar Graphs are Almost for Free!
von: Mozes, Shay, et al.
Veröffentlicht: (2026)

A Lower Bound for Light Spanners in General Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

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

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Shortcuts and Transitive-Closure Spanners Approximation
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Multiplicative Spanners in Minor-Free Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Minimum Temporal Spanners in Happy Graphs
von: Casteigts, Arnaud, et al.
Veröffentlicht: (2026)

Graph Spanners for Group Steiner Distances
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
von: Ahmed, Reyan, et al.
Veröffentlicht: (2024)

Light Edge Fault Tolerant Graph Spanners
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

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

Paths and Intersections: Exact Emulators for Planar Graphs
von: Li, George Z., et al.
Veröffentlicht: (2025)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Routing-Controlled Spanners
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

Light Spanners with Small Hop-Diameter
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

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

Directed Buy-at-Bulk Spanners
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

New Greedy Spanners and Applications
von: Popova, Elizaveta, et al.
Veröffentlicht: (2026)

Approximating Euclidean Shallow-Light Trees
von: Le, Hung, et al.
Veröffentlicht: (2025)

Maintaining Light Spanners via Minimal Updates
von: Khodabandeh, Hadi, et al.
Veröffentlicht: (2024)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

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