THE SOLUTION OF SOME RANDOM NP-HARD PROBLEMS IN POLYNOMIAL EXPECTED TIME

被引：120

作者：

DYER, ME

FRIEZE, AM

机构：

[1] UNIV LEEDS,LEEDS LS2 9JT,W YORKSHIRE,ENGLAND

[2] CARNEGIE MELLON UNIV,PITTSBURGH,PA 15213

[3] UNIV LONDON QUEEN MARY COLL,LONDON E1 4NS,ENGLAND

来源：

关键词：

D O I：

10.1016/0196-6774(89)90001-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：451 / 489

页数：39

共 9 条

[1]

Bui T., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P181

[2]

DYER ME, 1983, DISCRETE APPL MATH, V10, P139

[3]

Garey M. R., 1979, COMPUTERS INTRACTABI

[4] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

[5]

KUCERA L, 1977, LECTURE NOTES COMPUT, V56, P447

[6]

THOMASON A, IN PRESS ANN DISCRET

[7]

THOMASON A, IN PRESS DENSE EXPAN

[8] ALMOST ALL K-COLORABLE GRAPHS ARE EASY TO COLOR [J].

TURNER, JS .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1988, 9 (01) :63-82

[9]

TURNER JS, 1984 P ALL C COMM CO, P281