Optimal Euclidean tree covers

DOI10.4230/LIPICS.SOCG.2024.37MaRDI QIDQ6895865zbMATH OpenFDO

Authors Hsien-Chih Chang, Hung Le, Lazar Milenković, Shay Solomon, Cuong Than

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2024.37

zbMATH Keywords

bounded degreenet-treequadtreeroutingspannerSteiner pointtree cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Metric embeddings as related to computational problems and algorithms (68R12) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Approximate distance oracles
• Approximate nearest neighbor queries revisited
• Can't See the Forest for the Trees
• Collective tree spanners of graphs
• Covering metric spaces by few trees
• Covering planar metrics (and beyond): O(1) trees suffice
• Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching
• Euclidean Steiner spanners: light and sparse
• Geometric Spanner Networks
• scientific article; zbMATH DE number 5764857 (Why is no real title available?)
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• On hierarchical routing in doubling metrics
• Recent progress in exact geometric computation
• Routing with Polynomial Communication-Space Trade-Off
• Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more
• Smoothing the Gap Between NP and ER
• Truly optimal Euclidean spanners

Cited in

(2)

• Lower bounds on tree covers
• Light spanners with small hop-diameter

This page was built for publication: Optimal Euclidean tree covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6895865)