PARALLEL (DELTA+1)-COLORING OF CONSTANT-DEGREE GRAPHS

被引：25

作者：

GOLDBERG, AV

PLOTKIN, SA

机构：

[1] MIT, Cambridge, MA, USA, MIT, Cambridge, MA, USA

来源：

INFORMATION PROCESSING LETTERS | 1987年 / 25卷 / 04期

关键词：

COMPUTER PROGRAMMING - Algorithms - COMPUTER SYSTEMS; DIGITAL - Parallel Processing;

D O I：

10.1016/0020-0190(87)90169-4

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of DELTA using DELTA plus 1 colors and for finding a maximal independent set in a constant-degree graph. Given a graph with n vertices, the algorithms run in O(lg multiplied by (times) n) time on a EREW PRAM with O(n) processors. The algorithms use only local communication and achieve the same complexity bounds when implemented in a distributed model of parallel computation.

引用

页码：241 / 245

页数：5

共 8 条

[1] COMPLEXITY OF NETWORK SYNCHRONIZATION
AWERBUCH, B
[J]. JOURNAL OF THE ACM, 1985, 32 (04) : 804 - 823
[2] AWERBUCH B, 1986, COMMUNICATION
[3] COLE R, 1986, 18TH P ANN ACM S THE, P206
[4] A DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING-TREES
GALLAGER, RG
HUMBLET, PA
SPIRA, PM
[J]. ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1983, 5 (01): : 66 - 77
[5] GOLDBERG AV, 1987, MITLCSTM320 TECH REP
[6] Karloff H. J., 1985, THESIS U CALIFORNIA
[7] KARP RM, 1984, 16TH P ANN ACM S THE, P266
[8] LUBY M, 1985, 17TH P ANN ACM S THE, P1

← 1 →