Approximating geometric bottleneck shortest paths

DOI10.1016/J.COMGEO.2004.04.003zbMATH Open1082.65015OpenAlexW3021208656MaRDI QIDQ1886239FDOQ1886239

Authors: Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Norbert Zeh, Michiel Smid 

Publication date: 18 November 2004

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.04.003

Recommendations

• scientific article; zbMATH DE number 1962800
• On bounded leg shortest paths problems
• Approximate distance oracles for geometric spanners
• The Euclidean bottleneck Steiner path problem
• Bottleneck detour tree of points on a path

zbMATH Keywords

algorithmsshortest path

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Fast Algorithms for Finding Nearest Common Ancestors
• Title not available (Why is that?)
• Classes of graphs which approximate the complete Euclidean graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• Title not available (Why is that?)

Cited In (25)

• Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
• YAO GRAPHS SPAN THETA GRAPHS
• On a family of strong geometric spanners that admit local routing strategies
• Shortest paths in intersection graphs of unit disks
• Building Cartesian trees from free trees with \(k\) leaves
• Bottleneck shortest paths on a partially ordered scale
• Odd Yao-Yao Graphs are Not Spanners
• Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints
• Shortest path geometric rounding
• On the restricted 1-Steiner tree problem
• On the restricted \(k\)-Steiner tree problem
• The \(\varTheta_5\)-graph is a spanner
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Geometric k Shortest Paths
• π/2-ANGLE YAO GRAPHS ARE SPANNERS
• On bounded leg shortest paths problems
• On plane geometric spanners: a survey and open problems
• Efficient computation of geodesic shortest paths
• On bounded degree plane strong geometric spanners
• Continuous Yao graphs
• Approximation algorithms for geometric shortest path problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of Computation Theory

This page was built for publication: Approximating geometric bottleneck shortest paths

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