EFFICIENT ALGORITHM FOR PARTITIONING OF TREES

被引：49

作者：

LUKES, JA ^{[1
]}

机构：

[1] IBM CORP,SYST DEV DIV LAB,SKYPORT DR,SAN JOSE,CA 95114

来源：

IBM JOURNAL OF RESEARCH AND DEVELOPMENT | 1974年 / 18卷 / 03期

关键词：

D O I：

10.1147/rd.183.0217

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper describes an algorithm for partitioning a graph that is in the form of a tree. The algorithm has a growth in computation time and storage requirements that is directly proportional to the number of nodes in the tree. Several applications of the algorithm are briefly described. In particular it is shown that the tree partitioning problem frequently arises in the allocation of computer information to blocks of storage. Also, a heuristic method of partitioning a general graph based on this algorithm is suggested.

引用

页码：217 / 224

页数：8

共 10 条

[1]

[Anonymous], 1972, Graph Theory

[2]

JENSEN PA, 1970, OPER RES, V19, P916

[3]

Kernighan B. W., 1969, PhD thesis

[4] OPTIMAL SEQUENTIAL PARTITIONS OF GRAPHS [J].

KERNIGHAN, BW .

JOURNAL OF THE ACM, 1971, 18 (01) :34-+

[5]

Knuth D. E., 1968, The art of computer programming, V1

[6]

LAWLER EL, 1962, IRE T ELECT COMPUTER, VC 11, P86

[7]

LAWLER EL, 1969, IEEE T COMPUTERS, VC 18, P47

[8]

LUCCIO F, 1969, IEEE T CIRCUIT THEOR, VCT16, P184

[9]

LUKES JA, 1972, 32 STANF U DIG SYST

[10]

STONE HS, 1970, J ACM, V18, P182

← 1 →