Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree

DOI10.1007/s00453-013-9779-yzbMath1308.05043OpenAlexW2038022626MaRDI QIDQ2258072

Li Ning, Mingfei Li, T.-H. Hubert Chan

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10722/215510

zbMATH Keywords

doubling dimensionbounded maximum degreebounded hop-diametersparse fault-tolerant spanners

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing on a free tree via complexity-preserving mappings
• Fault-tolerant geometric spanners
• Balancing Degree, Diameter, and Weight in Euclidean Spanners
• Fault-tolerant spanners
• Geometric Spanner Networks
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Efficiency of a Good But Not Linear Set Union Algorithm
• Fault-tolerant spanners for general graphs
• Deformable spanners and applications
• Fast construction of nets in low dimensional metrics, and their applications
• Optimal euclidean spanners
• Narrow-Shallow-Low-Light Trees with and without Steiner Points
• Small hop-diameter sparse spanners for doubling metrics

This page was built for publication: Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree