Thek-centrum shortest path problem

  1. Robert Garfinkel 1
  2. Elena Fernández 2
  3. Timothy J. Lowe 3
  1. 1 University of Connecticut, USA
  2. 2 Universidad Politécnica de Cataluña, España
  3. 3 University of Iowa, USA
Mostrar afiliaciones +
Revista:
Top

ISSN: 1863-8279,  1134-5764

Año de publicación: 2006

Volumen: 14

Número: 2

Páginas: 279-292

Tipo: Artículo

DOI: 10.1007/BF02837564 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Top

Resumen

Thek-Centrum Shortest Path Problem (kCSP[s, t]) is to minimize the sum of thek longest arcs in any (simple)s−t path containing at leastk arcs, wherek is a positive integer.kCSP is introduced and is shown to be NP-Hard, although it is polynomially solvable ifk is constrained to be no greater than the number of arcs in ans−t path with fewest arcs. Some properties of the problem are studied and a new weakly dual problem is also introduced.

Fuente de los datos: Dialnet