INFORMATION BOUNDS ARE WEAK IN THE SHORTEST DISTANCE PROBLEM

被引：24

作者：

GRAHAM, RL ^{[1
]}

YAO, AC ^{[1
]}

YAO, FF ^{[1
]}

机构：

[1] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305

来源：

关键词：

D O I：

10.1145/322203.322206

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：428 / 444

页数：17

共 14 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] ON THE SHORTEST ROUTE THROUGH A NETWORK [J].

DANTZIG, GB .

[3]

Dijkstra E., 1959, NUMER MATH, V1, P269

[4] ALGORITHM-97 - SHORTEST PATH [J].

FLOYD, RW .

[5]

Grunbaum B, 1967, CONVEX POLYTOPES

[6]

Hu T.C., 1969, INTEGER PROGRAMMING

[7]

Kerr L, 1970, THESIS CORNELL U ITH

[8]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[9]

Munro I., 1971, Information Processing Letters, V1, P56, DOI 10.1016/0020-0190(71)90006-8

[10]

STOER J, 1970, CONVEXITY OPTIMIZATI, V1