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, i.e., 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 pseudo-polynomial 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 signicant 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. keywords: Layered networks, Balanced paths, Cost difference, Pseudo-polynomial approaches

Balanced paths in acyclic networks: tractable cases and related approaches / P. CAPPANERA; M.G.SCUTELLA'. - In: NETWORKS. - ISSN 0028-3045. - ELETTRONICO. - 45:(2005), pp. 104-111. [10.1002/net.20053]

Balanced paths in acyclic networks: tractable cases and related approaches

CAPPANERA, PAOLA;
2005

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, i.e., 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 pseudo-polynomial 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 signicant 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. keywords: Layered networks, Balanced paths, Cost difference, Pseudo-polynomial approaches
45
104
111
P. CAPPANERA; M.G.SCUTELLA'
File in questo prodotto:
File Dimensione Formato  
Networks-BPP-2005.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: DRM non definito
Dimensione 132.73 kB
Formato Adobe PDF
132.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/351168
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 9
social impact