OPTIMAL PARALLEL TIME-BOUNDS FOR THE MAXIMUM CLIQUE PROBLEM ON INTERVALS

被引：10

作者：

CHEN, L ^{[1
]}

机构：

[1] OHIO STATE UNIV,DEPT COMP & INFORMAT SCI,COLUMBUS,OH 43210

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 42卷 / 04期

关键词：

INTERVALS; LOWER AND UPPER BOUNDS; MAXIMUM CLIQUE; PARALLEL ALGORITHMS; PRAM;

D O I：

10.1016/0020-0190(92)90239-R

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：197 / 201

页数：5

共 10 条

[1] OPTIMAL BOUNDS FOR DECISION-PROBLEMS ON THE CRCW PRAM [J].

BEAME, P ;

HASTAD, J .

JOURNAL OF THE ACM, 1989, 36 (03) :643-670

[2] FASTER OPTIMAL PARALLEL PREFIX SUMS AND LIST RANKING [J].

COLE, R ;

VISHKIN, U .

INFORMATION AND COMPUTATION, 1989, 81 (03) :334-352

[3] PARALLEL MERGE SORT [J].

COLE, R .

SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :770-785

[4] UPPER AND LOWER TIME-BOUNDS FOR PARALLEL RANDOM-ACCESS MACHINES WITHOUT SIMULTANEOUS WRITES [J].

COOK, S ;

DWORK, C ;

REISCHUK, R .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :87-97

[5]

GOLUMBIC MC, 1980, COMPUTER SCI APPLIED

[6] THE POWER OF PARALLEL PREFIX [J].

KRUSKAL, CP ;

RUDOLPH, L ;

SNIR, M .

IEEE TRANSACTIONS ON COMPUTERS, 1985, 34 (10) :965-968

[7] PARALLEL PREFIX COMPUTATION [J].

LADNER, RE ;

FISCHER, MJ .

JOURNAL OF THE ACM, 1980, 27 (04) :831-838

[8]

Lovasz L., 1972, J COMBIN THEORY B, V13, P95, DOI DOI 10.1016/0095-8956(72)90045-7

[9]

MOITRA A, 1988, 26TH P ANN ALL C COM, P274

[10] FINDING THE MAXIMUM, MERGING, AND SORTING IN A PARALLEL COMPUTATION MODEL [J].

SHILOACH, Y ;

VISHKIN, U .

JOURNAL OF ALGORITHMS, 1981, 2 (01) :88-102

← 1 →