Relaxed spanners for directed disk graphs

DOI10.1007/S00453-011-9580-8MaRDI QIDQ1939674zbMATH OpenOpenAlexFDO

Authors 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

directed graphsdisk graphsspanners

Mathematics Subject Classification ID

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

Recommendations

• Relaxed Spanners for Directed Disk Graphs
• An improved construction for spanners of disks
• Spanners for Geometric Intersection Graphs
• Spanners for geometric intersection graphs with applications
• Small hop-diameter sparse spanners for doubling metrics

Cites work

• scientific article; zbMATH DE number 1305501 (Why is no real title available?)
• scientific article; zbMATH DE number 2119746 (Why is no real title available?)
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• All-Pairs Almost Shortest Paths
• Deformable spanners and applications
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Fully dynamic geometric spanners
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Sparse Distance Preservers and Additive Spanners

Cited in

(5)

• An improved construction for spanners of disks
• Relaxed Spanners for Directed Disk Graphs
• Spanners for directed transmission graphs
• Reachability problems for transmission graphs
• Reachability problems for transmission graphs

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

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