Parallel graph-partitioning using the mob heuristic

被引：0

作者：

Soch, M ^{[1
]}

Tvrdík, P ^{[1
]}

Volf, M ^{[1
]}

机构：

[1] Czech Tech Univ, Dept Comp Sci & Engn, Prague 12135, Czech Republic

来源：

RECENT ADVANCES IN PARALLEL VIRTUAL MACHINE AND MESSAGE PASSING INTERFACE | 1997年 / 1332卷

关键词：

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we study graph partitioning which is an important NP-complete problem. We have implemented two mob heuristics and analysed their performance. Our main result is that for randomly generated graphs the mob heuristics with an exponential schedule is more efficient than that with the Linear schedule, proposed earlier. With the other parameters of the heuristic being identical the exponential schedule doubles the speedup.

引用

页码：383 / 389

页数：7

共 6 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2] HOW EASY IS LOCAL SEARCH
JOHNSON, DS
PAPADIMITRIOU, CH
YANNAKAKIS, M
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 37 (01) : 79 - 100
[3] Kernighan B. W., 1970, Bell System Technical Journal, V49, P291
[4] OPTIMIZATION BY SIMULATED ANNEALING
KIRKPATRICK, S
GELATT, CD
VECCHI, MP
[J]. SCIENCE, 1983, 220 (4598) : 671 - 680
[5] PARALLELISM IN GRAPH-PARTITIONING
SAVAGE, JE
WLOKA, MG
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1991, 13 (03) : 257 - 272
[6] SOCH M, 1996, LECT NOTES COMPUTER, V1156, P38

← 1 →