Cover Image

Maintaining Light Spanners via Minimal Updates

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Khodabandeh, Hadi, Eppstein, David
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Decremental Greedy Polygons and Polyhedra Without Sharp Angles
by: Eppstein, David
Published: (2025)

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
by: Eppstein, David
Published: (2023)

Light Spanners with Small Hop-Diameter
by: Bhore, Sujoy, et al.
Published: (2025)

Dynamic Light Spanners in Doubling Metrics
by: Bhore, Sujoy, et al.
Published: (2026)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

Computational Complexities of Folding
by: Eppstein, David
Published: (2024)

The Complexity of Geodesic Spanners
by: de Berg, Sarita, et al.
Published: (2023)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, et al.
Published: (2024)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
by: La, An, et al.
Published: (2025)

Visualizing Treewidth
by: Chiu, Alvin, et al.
Published: (2025)

Dynamically Maintaining the Persistent Homology of Time Series
by: di Montesano, Sebastiano Cultrera, et al.
Published: (2023)

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
by: Le, Hung, et al.
Published: (2021)

Towards Instance-Optimal Euclidean Spanners
by: Le, Hung, et al.
Published: (2024)

Minimizing the Size of the Uncertainty Regions for Centers of Moving Entities
by: Evans, William, et al.
Published: (2023)

Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings
by: Dobler, Alexander, et al.
Published: (2024)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
by: Le, Hung, et al.
Published: (2023)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
by: Ahmed, Reyan, et al.
Published: (2024)

Euclidean distance compression via deep random features
by: Leroux, Brett, et al.
Published: (2024)

Retroactive Monotonic Priority Queues via Range Searching
by: Castro, Lucas, et al.
Published: (2025)

Relating Interleaving and Fréchet Distances via Ordered Merge Trees
by: Beurskens, Thijs, et al.
Published: (2023)

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching
by: Duan, Hongyi, et al.
Published: (2025)

Sequential non-determinism in tile self-assembly: a general framework and an application to efficient temperature-1 self-assembly of squares
by: Furcy, David, et al.
Published: (2024)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
by: Browne, Reilly, et al.
Published: (2026)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, et al.
Published: (2023)

Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
by: Depian, Thomas, et al.
Published: (2026)

An Improved FPT Algorithm for Computing the Interleaving Distance between Merge Trees via Path-Preserving Maps
by: P V, Althaf, et al.
Published: (2026)

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

A Simple Dynamic Spanner via APSP
by: Kyng, Rasmus, et al.
Published: (2024)

Routing-Controlled Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
by: Eppstein, David, et al.
Published: (2025)

Directed Buy-at-Bulk Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)