Spanners for Directed Transmission Graphs

DOI10.1137/16M1059692zbMath1398.68401arXiv1601.07798OpenAlexW3099199262WikidataQ129418690 ScholiaQ129418690MaRDI QIDQ4581909

Wolfgang Mulzer, Haim Kaplan, Paul Seiferth, Liam Roditty

Publication date: 21 August 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.07798

zbMATH Keywords

quadtreepannerreachability oracletransmission graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

Dynamic connectivity in disk graphs ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Unnamed Item ⋮ Reachability problems for transmission graphs ⋮ Reachability problems for transmission graphs ⋮ Unnamed Item ⋮ Reachability oracles for directed transmission graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Unit disk graphs
• Shortest paths in intersection graphs of unit disks
• Spanners for geometric intersection graphs with applications
• Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent
• Voronoi Diagram in the Laguerre Geometry and Its Applications
• Geometric Spanner Networks
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Optimal Search in Planar Subdivisions
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• π/2-ANGLE YAO GRAPHS ARE SPANNERS
• Spanners and Reachability Oracles for Directed Transmission Graphs
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Compact oracles for reachability and approximate distances in planar digraphs

This page was built for publication: Spanners for Directed Transmission Graphs