# Analysis of a class of graph partitioning problems

P. Bertolazzi; M. Lucertini; A. Marchetti Spaccamela

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1982)

- Volume: 16, Issue: 3, page 255-261
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topBertolazzi, P., Lucertini, M., and Marchetti Spaccamela, A.. "Analysis of a class of graph partitioning problems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 16.3 (1982): 255-261. <http://eudml.org/doc/92165>.

@article{Bertolazzi1982,

author = {Bertolazzi, P., Lucertini, M., Marchetti Spaccamela, A.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {chains; cycles; stars; binary trees},

language = {eng},

number = {3},

pages = {255-261},

publisher = {EDP-Sciences},

title = {Analysis of a class of graph partitioning problems},

url = {http://eudml.org/doc/92165},

volume = {16},

year = {1982},

}

TY - JOUR

AU - Bertolazzi, P.

AU - Lucertini, M.

AU - Marchetti Spaccamela, A.

TI - Analysis of a class of graph partitioning problems

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 1982

PB - EDP-Sciences

VL - 16

IS - 3

SP - 255

EP - 261

LA - eng

KW - chains; cycles; stars; binary trees

UR - http://eudml.org/doc/92165

ER -

## References

top- 1. N. CHRISTOFIDES and P. BROOKER, The Optimal Partitioning of Graphs, S.I.A.M. J. App. Math., January 1976. Zbl0321.05123MR405911
- 2. M. R. GAREY and D. S. JOHNSON, Computers and Intractability, Freeman and Co., 1979. Zbl0411.68039MR519066
- 3. F.O. HADLOCK, Minimum Spanning Forest of Bounded Trees, Proc. 5th Southeastern Conf. on Combinatorics, Graph theory and Computing, Winnipeg., 1974. Zbl0322.05104MR357180
- 4. L. HYAFIL and K. L. RIVEST, Graph Partitioning and Constructing Optimal Decision Trees are Polynomial Complete Problem, Re. 33 I.R.I.A.-Laboria, Rocquencourt, France, 1973.
- 5. R. M. KARP, Reducibility among Combinatorial Problems, in R. E. MILLER and J. W. THATCHER Eds., Complexity of Computer Computations, Plenum Press, N.Y., 1972. Zbl0366.68041MR378476
- 6. B. W. KERNIGHAN, Some Graph Partitioning Problems Related to Program Segmentation, Ph. D. Thesis, Princeton Univ., N.J., January 1969.
- 7. E. L. LAWLER, Fast Approximation Algorithms for Knapsack Problems, Proc. 18th Ann. Symp. on Foundations of Computer Science, I.E.E.E. Comp. Soc, Long Beach, 1977. Zbl0389.90071MR525705
- 8. E. L. LAWLER, K. N. LEVITT and J. TURNER, Module Clustering to Minimize Delay in Digital Networks, I.E.E.E. Tr. on Comp. C-18, 1969. Zbl0172.20603
- 9. J. A. LUKES, Efficient Algorithm for the Partitioning of Trees, I.B.M. J. Res. Develop., Vol. 18, 1974. Zbl0289.68008MR345440
- 10. G. S. RAO, H. S. STONE and T. C. HU, Assignment of Tasks in a Distributed Processor System with Limited Memory, I.E.E.E. Tr. on Comp., C-28, 1979. Zbl0397.68024MR528357