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

How to cite

top

Bertolazzi, 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. 1. N. CHRISTOFIDES and P. BROOKER, The Optimal Partitioning of Graphs, S.I.A.M. J. App. Math., January 1976. Zbl0321.05123MR405911
  2. 2. M. R. GAREY and D. S. JOHNSON, Computers and Intractability, Freeman and Co., 1979. Zbl0411.68039MR519066
  3. 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. 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. 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. 6. B. W. KERNIGHAN, Some Graph Partitioning Problems Related to Program Segmentation, Ph. D. Thesis, Princeton Univ., N.J., January 1969. 
  7. 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. 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. 9. J. A. LUKES, Efficient Algorithm for the Partitioning of Trees, I.B.M. J. Res. Develop., Vol. 18, 1974. Zbl0289.68008MR345440
  10. 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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.