Can I read Minimum-cost strong network orientation problems: Classification, complexity, and algorithms on EtoBox?

Minimum-cost strong network orientation problems: Classification, complexity, and algorithms by Burkard, Rainer E.; Feldbacher, Karin; Klinz, Bettina; Woeginger, Gerhard J. is a Computer Science article available to read on EtoBox.

What is Minimum-cost strong network orientation problems: Classification, complexity, and algorithms about?

In the minimum-cost strong network orientation problem (MCSO), we are given an undirected graph G Å (V, E) with nonnegative edge lengths ᐉ(e) and a transportation schedule T Å {(s 1 , t 1 , w 1 ), . . . , (s k , t k , w k )}, where w i units of weight have to be transported from the source vertex s i to the target vertex t i for i Å 1, . . . , k. Let G s be a strongly connected orientation of G and let L s i be the length of the shortest (directed) path from s i to t i in G s . The goal in the MCSO is to find a strongly connected orientation G s such that the overall cost of the orientation given by ͚ k iÅ1 w i L s i (sum case) or max iÅ1,...,k w i L s i (bottleneck case) is minimized. The strong network orientation problem is motivated by the practical problem of designing the optimal unidirectional flow path of automated guided vehicles. In this paper, we investigate the MCSO from the algorithmic and complexity points of view and propose a classification scheme. In the first part of the paper, we identify several efficiently solvable cases of the MCSO with sum and bottleneck objective functions which arise if additional restrictions are imposed on the structure of the graph G, th

Who reads Minimum-cost strong network orientation problems: Classification, complexity, and algorithms?

Author

Burkard, Rainer E.; Feldbacher, Karin; Klinz, Bettina; Woeginger, Gerhard J.

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 0028-3045)

Published

1999

Language

EN

Field

Computer Science (Physical Sciences)