Minimal cost linkages in graphs

S.A. Harrison and V.J. Rayward‐Smith

Annals of Operations Research, 1999, vol. 86, issue 0, 295-319

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). Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018963020368 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:86:y:1999:i:0:p:295-319:10.1023/a:1018963020368

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018963020368

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().