AN EFFICIENT PARALLEL ALGORITHM FOR COMPUTING A MAXIMAL INDEPENDENT SET IN A HYPERGRAPH OF DIMENSION-3

被引：15

作者：

DAHLHAUS, E

KARPINSKI, M

KELSEN, P

机构：

[1] UNIV TEXAS,DEPT COMP SCI,TAYLOR HALL 2124,AUSTIN,TX 78712

[2] UNIV BONN,DEPT COMP SCI,W-5300 BONN,GERMANY

[3] INT COMP SCI INST,BERKELEY,CA

来源：

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

基金：

美国国家科学基金会;

关键词：

DESIGN OF ALGORITHMS; PARALLEL ALGORITHMS; COMBINATORIAL PROBLEMS; COMPUTATIONAL COMPLEXITY;

D O I：

10.1016/0020-0190(92)90228-N

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper considers the problem of computing a maximal independent set in a hypergraph. We present an efficient deterministic NC algorithm for finding a maximal independent set in a hypergraph of dimension 3: the algorithm runs in time O(log4n) time on n + m processors of an EREW PRAM and is optimal up to a polylogarithmic factor. Our algorithm adapts the technique of Goldberg and Spencer for finding a maximal independent set in a graph (or hypergraph of dimension 2). It is the first NC algorithm for finding a maximal independent set in a hypergraph of dimension greater than 2.

引用

页码：309 / 313

页数：5

共 12 条

[1] A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM [J].

ALON, N ;

BABAI, L ;

ITAI, A .

JOURNAL OF ALGORITHMS, 1986, 7 (04) :567-583

[2]

BEAME P, 1990, 1ST P ACM SIAM SODA, P212

[3]

BEAME P, 1991, COMMUNICATION MAY

[4]

BEAME P, 1989, TR89003 INT COMP SCI

[5]

DAHLHAUS E, 1989, TR89052 INT COMP SCI

[6] A NEW PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM [J].

GOLDBERG, M ;

SPENCER, T .

SIAM JOURNAL ON COMPUTING, 1989, 18 (02) :419-427

[7]

Goldberg M., 1989, SIAM J DISCRETE MATH, V2, P322

[8]

Karp R.M., 1990, HDB THEORETICAL COMP, P869

[9] THE COMPLEXITY OF PARALLEL SEARCH [J].

KARP, RM ;

UPFAL, E ;

WIGDERSON, A .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 36 (02) :225-253

[10]

KELSEN P, 1990, UNPUB EFFICIENT PARA

← 1 2 →