Spanners with Slack

DOI10.1007/11841036_20MaRDI QIDQ5449528zbMATH OpenOpenAlexFDO

Authors T.-H. Hubert Chan, Michael Dinitz, Anupam Gupta

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11841036_20

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Low distortion spanners
• Low Distortion Spanners
• Metric embeddings with relaxed guarantees
• Small Stretch Pairwise Spanners
• Relaxed Spanners for Directed Disk Graphs

Cited in

(17)

• Graph spanners: a tutorial review
• A note on distance-preserving graph sparsification
• Demand-aware network designs of bounded degree
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Deformable spanners and applications
• Streaming Embeddings with Slack
• Metric embeddings with relaxed guarantees
• Approximating approximate distance oracles
• Volume in general metric spaces
• Small Stretch Pairwise Spanners
• Advances in metric embedding theory
• A local search algorithm for radius-constrained k-median
• Stable roommates spanner
• A local search algorithm for the radius-constrained k-median problem
• Revisiting priority k-center: fairness and outliers
• Giving some slack: shortcuts and transitive closure compressions
• Efficient distributed computation of distance sketches in networks

This page was built for publication: Spanners with Slack

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