✦ LIBER ✦

On orientations and shortest paths

✍ Scribed by Rafael Hassin; Nimrod Megiddo

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 977 KB
Volume: 114-115
Category: Article
ISSN: 0024-3795
DOI: 10.1016/0024-3795(89)90481-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Near-shortest and K-shortest simple path

Near-shortest and K-shortest simple paths

✍ W. Matthew Carlyle; R. Kevin Wood 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB

Greedy Packet Scheduling on Shortest Pat

Greedy Packet Scheduling on Shortest Paths

✍ Y. Mansour; B. Pattshamir 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 745 KB

We investigate the simple class of greedy scheduling algorithms, that is, algorithms that always forward a packet if they can. Assuming that only one packet can be delivered over a link in a single step and that the routes traversed by a set of packets are distance optimal ("shortest paths"), we pro

A note on k-shortest paths problem

✍ Nick Gravin; Ning Chen 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 1 views

It is well-known that in a directed graph, if deleting any edge will not affect the shortest distance between two specific vertices s and t, then there are two edge-disjoint paths from s to t and both of them are shortest paths. In this article, we generalize this to shortest k edgedisjoint s-t path

On finding shortest paths in nonnegative

On finding shortest paths in nonnegative networks

✍ A. Rosenthal 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 438 KB

A modification of Dantzig's algorithm for the all! pairs shortest paths problem is given. The new algorithm applies only to graphs with nonnegative arc lengths. For an IV-node compkte graph ir has a worst case running time of fN3 triple operations of the form D-: = min(D--D-~+D~$ and iv" log N other

The lower bounds on distributed shortest

The lower bounds on distributed shortest paths

✍ K.V.S. Ramarao; S. Venkatesan 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 507 KB

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