Thek-centrum shortest path problem |
| |
| Authors: | Robert Garfinkel Elena Fernández Timothy J Lowe |
| |
| Institution: | (1) School of Business Administration, University of Connecticut, Storrs, Connecticut, USA;(2) Stotistics and Operations Research Department, Technical University of Catolonia, Barcelona, Spain;(3) Tippie College of Business, University of Iowa, Iowa City, Iowa, USA |
| |
| Abstract: | Thek-Centrum Shortest Path Problem (kCSPs, 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. |
| |
| Keywords: | Shortes path k-centrum |
| 本文献已被 SpringerLink 等数据库收录！ |
|
