FAIR DISSECTIONS OF SPIDERS, WORMS, AND CATERPILLARS

被引：20

作者：

DESIMONE, C

LUCERTINI, M

PALLOTTINO, S

SIMEONE, B

机构：

[1] UNIV ROMA TOR VERGATA,DIPARTIMENTO ELETTR,I-00173 ROME,ITALY

[2] UNIV PISA,DEPARTIMENTO INFORMAT,I-56100 PISA,ITALY

[3] UNIV ROME LA SAPIENZA,DIPARTIMENTO STAT,I-00100 ROME,ITALY

[4] RUTGERS STATE UNIV,RUTGERS CTR OPEPAT RES,HILL CTR MATH SCI,NEW BRUNSWICK,NJ 08903

来源：

NETWORKS | 1990年 / 20卷 / 03期

关键词：

D O I：

10.1002/net.3230200305

中图分类号：

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

学科分类号：

0812 ;

摘要：

In the present paper we deal with equipartition problems for special classes of trees, i. e., spiders, stars, worms, and caterpillars. We prove that the equipartition problem is NP‐complete for spiders (and, hence, for general trees); on the other hand, we give efficient polynomial‐time algorithms for stars, worms, and caterpillars. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company

引用

页码：323 / 344

页数：22

共 12 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER
[2] FAST ALGORITHM FOR CERTAIN DYNAMIC-PROGRAMMING MINIMIZATIONS
BAUER, WR
BLANKINSHIP, WA
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 33 (02) : 323 - 336
[3] A SHIFTING ALGORITHM FOR MIN-MAX TREE PARTITIONING
BECKER, RI
SCHACH, SR
PERL, Y
[J]. JOURNAL OF THE ACM, 1982, 29 (01) : 58 - 67
[4] Berge C., 1983, GRAPHES
[5] Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9
[6] DESIMONE C, 1986, OCT TIMS ORSA M MIAM
[7] Galligani I., 1975, APPL CALCOLO, P77
[8] Karp R.M., 1972, COMPLEXITY COMPUTER, P85
[9] Lawler E. L., 1976, COMBINATORIAL OPTIMI
[10] Marshall A. W., 1979, INEQUALITIES MAJORIZ

← 1 2 →