EFFICIENT ALGORITHM FOR PARTITIONING OF TREES

被引:48
作者
LUKES, JA [1 ]
机构
[1] IBM CORP,SYST DEV DIV LAB,SKYPORT DR,SAN JOSE,CA 95114
关键词
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
    KERNIGHAN, BW
    [J]. 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