Journal article
The k-Centrum Shortest Path Problem
TOP, Vol.14(2), pp.279-292
12/01/2006
DOI: 10.1007/BF02837564
Abstract
The k-Centrum Shortest Path Problem (kCSP[s, t]) is to minimize the sum of the k longest arcs in any (simple) s-t path containing at least k arcs, where k is a positive integer. kCSP is introduced and is shown to be NP-Hard, although it is polynomially solvable if k is constrained to be no greater than the number of arcs in an s-t path with fewest arcs. Some properties of the problem are studied and a new weakly dual problem is also introduced.
Details
- Title: Subtitle
- The k-Centrum Shortest Path Problem
- Creators
- Robert Garfinkel - University of ConnecticutElena Fernandez - Universitat Politècnica de CatalunyaTimothy J. Lowe - University of Iowa
- Resource Type
- Journal article
- Publication Details
- TOP, Vol.14(2), pp.279-292
- DOI
- 10.1007/BF02837564
- ISSN
- 1134-5764
- Publisher
- SOCIEDAD ESTADISTICA INVESTIGACION OPERATIVA
- Number of pages
- 14
- Language
- English
- Date published
- 12/01/2006
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963190502771
Metrics
1 Record Views