𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A branch and bound algorithm for the robust shortest path problem with interval data

✍ Scribed by R. Montemanni; L.M. Gambardella; A.V. Donati

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
239 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The robust shortest path problem in seri
The robust shortest path problem in series–parallel multidigraphs with interval data
✍ Adam Kasperski; PaweΕ‚ ZieliΕ„ski πŸ“‚ Article πŸ“… 2006 πŸ› Elsevier Science 🌐 English βš– 196 KB

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is construct

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 288 KB πŸ‘ 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a