𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity of some inverse shortest path lengths problems

✍ Scribed by Tingting Cui; Dorit S. Hochbaum

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
262 KB
Volume
56
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Inapproximability results for the invers
Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths
✍ Andreas Bley πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 304 KB

## Abstract We study the complexity of two inverse shortest paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph __D__ = (__V__, __A__), the task is to find positive integer arc lengths such that th

Average-case complexity of shortest-path
Average-case complexity of shortest-paths problems in the vertex-potential model
✍ Colin Cooper; Alan Frieze; Kurt Mehlhorn; Volker Priebe πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 146 KB πŸ‘ 2 views

We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and wit

The time-dependent shortest pair of disj
The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 160 KB πŸ‘ 3 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu

Time–Work Tradeoffs of the Single-Source
Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
✍ Hanmao Shi; Thomas H Spencer πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 111 KB

We give parallel algorithms that solve the single-source shortest paths problem Ε½ . on a weighted, undirected graph with n vertices and m edges in O t lg n time and Ε½Ε½ 3 2 . Ε½ . . Ε½ . Ε½ Ε½ 3 3 O n rt lg n lg nrt q m lg n work, or in O t lg n time and O n rt q . . mnrt lg n work for any t in the range