Leonidas Georgiadis: Algorithms for Two Optimization Problems on Directed Graphs

This is a joint work with Stavroula Siahalou.

We consider the following optimization problems of directed graphs.

1. Given link costs taking values in a set $V$ endowed with ``less than'' relation and an ``addition'' operation, find an optimal spanning tree.

2. Given link costs (nonnegative real numbers) and additional constraints (nonnegative real numbers), find a path from a given source to a given destination that has minimal cost and satisfies all the constraints.

We provide optimal algorithms for both problems.

Regarding Problem 1, special cases of the proposed algorithm provide Edmond's algorithm [Edm67] and a algorithm for the bottleneck arborescence algorithm [GT88] that appears to be new. The setup provides also a polynomial time algorithm for the lexicographically optimal arborescence problem.

Problem 2 is known to be NP-complete. However, polynomial approximation algorithms exist [LR01]. The latter algorithms are based on the Dynamic Programming equation related to Problem 2. We propose an algorithm which exploits the properties of the dynamic programming functions related with each node, to provide optimal algorithms that can be considered as generalizations of Dijkstra's algorithm. The performance of these algorithms depends mainly on the number of function discontinuities, which is usually not very large, and as a result the running time is very satisfactory for graphs of fairly large size.

Bibliography

Edm67
Jack Edmonds.
Optimum branchings.
J. Res. Nat. Bur. Standards Sect. B, 71B:233-240, 1967.

GT88
Harold N. Gabow and Robert E. Tarjan.
Algorithms for two bottleneck optimization problems.
J. Algorithms, 9(3):411-417, 1988.

LR01
Dean H. Lorenz and Danny Raz.
A simple efficient approximation scheme for the restricted shortest path problem.
Oper. Res. Lett., 28(5):213-219, 2001.

Back to the Index


Please send comments and corrections to Thomas Klausner.