Minimal cost linkages in graphs

Harrison, S. A. and Rayward-Smith, V. J. (1999) Minimal cost linkages in graphs. Annals of Operations Research, 86. pp. 295-319. ISSN 0254-5330

Full text not available from this repository. (Request a copy)

Abstract

In this paper, we consider the problem of finding minimal cost linkages in graphs. Wediscuss how this problem arises in practice and, in particular, its relevance to the military.Given a graph G with an associated cost function and a multiset of vertex pairs, weaddress the problem of finding a linkage of minimal cost. From this optimisation problem,we are able to define the decision problems Min‐Sum Non‐Intersecting Paths (MSNP) andMin‐Max Non‐Intersecting Paths (MMNP), and prove their NP‐completeness. We also showthat for fixed k >= 2, where k denotes the number of terminal pairs, MMNP remains NP‐complete.We also define restricted versions of the problems, MMNP(r) and MSNP(r), where link-agesmay only be defined over the r cheapest paths between each vertex pair. For fixedk >= 3, we show the restricted problems remain NP‐complete and discuss the limitations ofthe restriction.We include a case study which demonstrates the advantages of using heuristic methods,such as genetic algorithms and simulated annealing, to find solutions to the optimisationproblem MSNP(r).

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	EPrints Services
Date Deposited:	01 Oct 2010 13:41
Last Modified:	24 Sep 2024 10:29
URI:	https://ueaeprints.uea.ac.uk/id/eprint/3002
DOI:	10.1023/A:1018963020368

Actions (login required)

View Item