Thek-centrum shortest path problem

• Robert Garfinkel ^[1] ; Elena Fernández ^[2] ; Timothy J. Lowe ^[3]
  1. [1] University of Connecticut

     University of Connecticut

     Town of Mansfield, Estados Unidos

     
  2. [2] Universitat Politècnica de Catalunya

     Universitat Politècnica de Catalunya

     Barcelona, España

     
  3. [3] University of Iowa

     University of Iowa

     City of Iowa City, Estados Unidos

     

  Mostrar afiliaciones +
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 14, Nº. 2, 2006, págs. 279-292
• Idioma: inglés
• DOI: 10.1007/bf02837564
• Enlaces
  • Texto completo (pdf)
• 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.