2 APPLICATIONS OF INDUCTIVE COUNTING FOR COMPLEMENTATION PROBLEMS

被引：61

作者：

BORODIN, A

COOK, SA

DYMOND, PW

RUZZO, WL

TOMPA, M

机构：

[1] UNIV CALIF SAN DIEGO,DEPT COMP SCI & ENGN,C-014,LA JOLLA,CA 92093

[2] UNIV WASHINGTON,DEPT COMP SCI,FR-35,SEATTLE,WA 98195

[3] IBM CORP,THOMAS J WATSON RES CTR,YORKTOWN HTS,NY 10598

来源：

SIAM JOURNAL ON COMPUTING | 1989年 / 18卷 / 03期

关键词：

D O I：

10.1137/0218038

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：559 / 578

页数：20

共 41 条

[1] SORTING IN C LOG N PARALLEL STEPS [J].

AJTAI, M ;

KOMLOS, J ;

SZEMEREDI, E .

COMBINATORICA, 1983, 3 (01) :1-19

[2]

Aleliunas R., 1979, 20th Annual Symposium of Foundations of Computer Science, P218, DOI 10.1109/SFCS.1979.34

[3]

BUSS SR, 1987, CS103 U CAL DEP COMP

[4] ALTERNATION [J].

CHANDRA, AK ;

KOZEN, DC ;

STOCKMEYER, LJ .

JOURNAL OF THE ACM, 1981, 28 (01) :114-133

[5] CHARACTERIZATIONS OF PUSHDOWN MACHINES IN TERMS OF TIME-BOUNDED COMPUTERS [J].

COOK, SA .

JOURNAL OF THE ACM, 1971, 18 (01) :4-&

[6] A TAXONOMY OF PROBLEMS WITH FAST PARALLEL ALGORITHMS [J].

COOK, SA .

INFORMATION AND CONTROL, 1985, 64 (1-3) :2-22

[7]

Dymond P. W., 1980, 21st Annual Symposium on Foundations of Computer Science, P360, DOI 10.1109/SFCS.1980.22

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

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345

[9]

Friedman J., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P506, DOI 10.1109/SFCS.1984.715953

[10] COMPUTATIONAL COMPLEXITY OF PROBABILISTIC TURING MACHINES [J].

GILL, J .

SIAM JOURNAL ON COMPUTING, 1977, 6 (04) :675-695

← 1 2 3 4 5 →