Premium
Balanced paths in acyclic networks: Tractable cases and related approaches
Author(s) -
Cappanera Paola,
Scutellà Maria Grazia
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20053
Subject(s) - disjoint sets , node (physics) , path (computing) , combinatorics , set (abstract data type) , shortest path problem , arc (geometry) , computer science , floyd–warshall algorithm , mathematics , discrete mathematics , algorithm , dijkstra's algorithm , computer network , structural engineering , engineering , programming language , graph , geometry
Abstract Given a weighted acyclic network G and two nodes s and t in G , we consider the problem of computing k balanced paths from s to t , that is, k paths such that the difference in cost between the longest and the shortest path is minimized. The problem has several variants. We show that, whereas the general problem is solvable in pseudopolynomial time, both the arc‐disjoint and the node‐disjoint variants (i.e., the variants where the k paths are required to be arc‐disjoint and node‐disjoint, respectively) are strongly NP‐Hard. We then address some significant special cases of such variants, and propose exact as well as approximate algorithms for their solution. The proposed approaches are also able to solve versions of the problem in which k origin‐destination pairs are provided, and a set of k paths linking the origin‐destination pairs has to be computed in such a way to minimize the difference in cost between the longest and the shortest path in the set. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 104‐111 2005