Cover Image

Light Spanners with Small Hop-Diameter

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhore, Sujoy, Milenkovic, Lazar
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Dynamic and Streaming Algorithms for Union Volume Estimation
by: Bhore, Sujoy, et al.
Published: (2026)

Maintaining Light Spanners via Minimal Updates
by: Khodabandeh, Hadi, et al.
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)

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

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

Visibility Queries in Simple Polygons
by: Bhore, Sujoy, et al.
Published: (2026)

On Strong Diameter Padded Decompositions
by: Filtser, Arnold
Published: (2019)

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

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

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

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
by: Bhore, Sujoy, et al.
Published: (2025)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

Online TCP Acknowledgment under General Delays
by: Bhore, Sujoy, et al.
Published: (2026)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Extraction Theorems With Small Extraction Numbers
by: Agarwal, Arjun, et al.
Published: (2024)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

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

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

Guarding Polyominoes Under $k$-Hop Visibility
by: Filtser, Omrit, et al.
Published: (2023)

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

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
by: de Berg, Mark, et al.
Published: (2026)

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)

Explaining Rankings with Hidden Group Bonuses
by: Yan, Alvin Hong Yao, et al.
Published: (2026)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
by: Bhore, Sujoy, et al.
Published: (2026)

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