Spanners for Directed Transmission Graphs
From MaRDI portal
Publication:4581909
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
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
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
