Relaxed spanners for directed disk graphs

DOI10.1007/S00453-011-9580-8zbMath1259.05055OpenAlexW2122157304MaRDI QIDQ1939674

David Peleg, Liam Roditty

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2489/

zbMATH Keywords

disk graphsdirected graphsspanners

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Reachability problems for transmission graphs ⋮ Reachability problems for transmission graphs

Cites Work

• Deformable spanners and applications
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• All-Pairs Almost Shortest Paths
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Sparse Distance Preservers and Additive Spanners
• Fully dynamic geometric spanners
• Unnamed Item
• Unnamed Item

This page was built for publication: Relaxed spanners for directed disk graphs