THE COMPLEXITY OF PARALLEL SEARCH

被引：53

作者：

KARP, RM

UPFAL, E

WIGDERSON, A

机构：

[1] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA 95120

[2] HEBREW UNION COLL,DEPT COMP SCI,CINCINNATI,OH 45220

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1988年 / 36卷 / 02期

关键词：

* Some of the results in this paper appear in preliminary form in [KUW85a] and [KUW85c]. + Research supported by NSF Grant DCR-8411954. * Research supported by a Weizmann Fellowship. Research supported by DARPA Grant NOOO39-83-C-1036 at the University of California Berkeley;

D O I：

10.1016/0022-0000(88)90027-X

中图分类号：

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

学科分类号：

0812 ;

摘要：

引用

页码：225 / 253

页数：29

共 18 条

[1] FAST PROBABILISTIC ALGORITHMS FOR HAMILTONIAN CIRCUITS AND MATCHINGS [J].

ANGLUIN, D ;

VALIANT, LG .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) :155-193

[2]

AWERBUCH B, 1984, 16TH P ANN ACM S THE, P249

[3] TAIL OF THE HYPERGEOMETRIC DISTRIBUTION [J].

CHVATAL, V .

DISCRETE MATHEMATICS, 1979, 25 (03) :285-287

[4]

FICH FE, 1984, 3RD P ANN ACM S PRIN, P179

[5]

GALIL Z, 1984, 16TH P ACM S THEOR C, P240

[6]

HAUSMANN D, 1981, MATH PROGRAM STUD, V14, P98, DOI 10.1007/BFb0120924

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

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[8] 3 VERSIONS OF A GROUP-TESTING GAME [J].

HWANG, FK .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (02) :145-153

[9]

Karp R. M., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P541, DOI 10.1109/SFCS.1985.57

[10] CONSTRUCTING A PERFECT MATCHING IS IN RANDOM NC [J].

KARP, RM ;

UPFAL, E ;

WIGDERSON, A .

COMBINATORICA, 1986, 6 (01) :35-48

← 1 2 →