Shortest path problem with cache dependent path lengths

被引：0

作者：

Fu, Z ^{[1
]}

Kurnia, A ^{[1
]}

Lim, A ^{[1
]}

Rodrigues, B ^{[1
]}

机构：

[1] Natl Univ Singapore, Dept Comp Sci, Singapore 117543, Singapore

来源：

CEC: 2003 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-4, PROCEEDINGS | 2003年

关键词：

shortest path problem; cache; tabu search; Genetic Algorithms; webpages;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper, we are motivated by the problem of finding the shortest path in a network when traversing webpages where cache size determines path length. The Shortest Path Problem with Cache-dependent Path Lengths is shown to be NP-Complete. It is a new problem for which we propose several effective heuristics, including a Dijkstra heuristic, Genetic Algorithms and Tabu Search.

引用

页码：2756 / 2761

页数：6

共 17 条

[1] ALMEIDA V, 1996, P IEEE C PAR DISTR I
[2] [Anonymous], 1989, GENETIC ALGORITHM SE
[3] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4] A penalty function heuristic for the resource constrained shortest path problem
Avella, P
Boccia, M
Sforza, A
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 142 (02) : 221 - 230
[5] Bestavros A., 1995, P 4 ACM INT C INF KN
[6] Cai X, 1997, NETWORKS, V29, P141, DOI 10.1002/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO
[7] 2-H
[8] CUNHA CR, 1997, INT S COMPUTERS COMM
[9] Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
[10] ALGORITHM-97 - SHORTEST PATH
FLOYD, RW
[J]. COMMUNICATIONS OF THE ACM, 1962, 5 (06) : 345 - 345

← 1 2 →