What question did this study set out to answer?

To determine the minimum proximity threshold parameter needed to guarantee a path of at most a specified length or weight between two given disks in a disk graph.

August 14, 2026ACM Transactions on AlgorithmsOpen Access

The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

View Full Paper

Ask AI

Bookmark

Authors

HKHaim KaplanAT&T (United States)MKMatthew J. KatzBen-Gurion University of the Negev RSRachel SabanBen-Gurion University of the Negev

Discussion

Member takes

Implication

Algorithmic analysis uncovers subquadratic solutions for reverse shortest path problems on geometric disk graphs, indicating improved computational efficiency for network optimization.

Key Points

To determine the minimum proximity threshold parameter needed to guarantee a path of at most a specified length or weight between two given disks in a disk graph.
Implemented decision procedures via customized breadth-first search for unweighted graphs and Dijkstra's algorithm for weighted graphs.
Maintained dynamic data structures for bichromatic closest pairs across geometric bicliques to evaluate graph connectivity.
Combined the decision procedure with enhanced interval shrinking and bifurcation methods to optimize the distance parameter.
Achieved an expected randomized running time of O*(n^(5/4)) for general disk graphs with arbitrary radii.
Improved the randomized expected running time to O*(n^(6/5)) for unit disk graphs with identical radii.
Extended algorithmic bounds to weighted proximity variants and disk radius scaling parameters.

Cite This Study

Kaplan et al. (2026) studied this question.

synapsesocial.com/papers/6a7ec69fb70b84ec8b912b4d https://doi.org/10.1145/3839562

View Full Paper

Ask AI

Bookmark

Implication

Algorithmic analysis uncovers subquadratic solutions for reverse shortest path problems on geometric disk graphs, indicating improved computational efficiency for network optimization.

The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

Discussion

Member takes

Implication

Key Points

Cite This Study

The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

Discussion

Member takes

Implication

Key Points

Cite This Study

Also Consider

Also Consider