home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1787 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  2.9 KB
  1. Path: sparky!uunet!mcsun!uknet!yorkohm!minster!paulh
  2. From: paulh@minster.york.ac.uk
  3. Newsgroups: comp.theory
  4. Subject: Re: Multiple-Way Graph Partitioning refs?
  5. Message-ID: <714298709.14712@minster.york.ac.uk>
  6. Date: 20 Aug 92 08:18:30 GMT
  7. References: <3298@creatures.cs.vt.edu>
  8. Organization: Department of Computer Science, University of York, England
  9. Lines: 66
  10. X-Newsreader: Tin 1.1 PL5
  11.  
  12. Here are some references that I picked up a while ago.
  13. I hope they are helpful.
  14.  
  15. %T Cutting and Partitioning a Graph After a Fixed Pattern
  16. %A Yannakakis, M.
  17. %A P. C. Kanellakis
  18. %A S. C. Cosmadakis
  19. %A C. H. Papdimitriou
  20. %P 712-722
  21. %B 10th International Colloquium on Automata, Languages and Programming
  22. %E J. Diaz
  23. %D July, 1983
  24. %C Barcelona, Spain
  25. %J Lecture Notes in Computer Science
  26. %V 154
  27. %I Springer-Verlag
  28. %K ICALP
  29.  
  30. %T The NP-completeness of some edge-partition problems 
  31. %A Holyer, I. 
  32. %X Shows that for each fixed n>or=3 it is NP-complete to determine whether an arbitrary graph can be edge-partitioned into subgraphs isomorphic to the complete graph K/sub n/. The NP-completeness of a number of other edge-partition problems follows immediately 
  33. %K graph theory, computational complexity, NP-completeness, edge-partition problems, graph 
  34. %O SIAM J. Comput. (USA) %J SIAM Journal on Computing
  35. %V 10 
  36. %N 4 
  37. %P 713-17 
  38. %D Nov. 1981
  39.  
  40. %T Efficient algorithm for graph-partitioning problem using a problem
  41. transformation method
  42. %A Lee, C.-H.
  43. %A Park, C.-I.
  44. %A Kim, M.
  45. %X Shows that the uniform k-way partitioning problem can be transformed into
  46. the max-cut problem using a graph modification technique. An iterative
  47. algorithm, based on the Kernighan-Lin method, for partitioning graphs is
  48. presented that exploits the problem equivalence property. The algorithm deals
  49. with nodes of various sizes without any performance degradation. The computing
  50. time per pass of the algorithm is O(kN/sup 2/), where N is the number of nodes
  51. in the given graph. In practice, only a small number of passes are typically
  52. needed, leading to a fast approximation algorithm for k-way partitioning.
  53. Experimental results show that the proposed algorithm outperforms the KL
  54. algorithm in the quality of solutions
  55. %K graph-partitioning problem, problem transformation method, uniform k-way
  56. partitioning problem, max-cut problem, graph modification technique, iterative
  57. algorithm, Kernighan-Lin method, problem equivalence property, nodes, computing
  58. time, passes, approximation algorithm
  59. %J Computer Aided Design
  60. %V 21
  61. %N 10
  62. %P 611-18
  63. %D Dec. 1989
  64.  
  65. %T An Efficient Heuristic Procedure for Partitioning Graphs
  66. %A B. W. Kernighan
  67. %A S. Lin
  68. %J Bell Systems Technical Journal
  69. %V 49
  70. %N 2
  71. %D 1970
  72. %P 291-307
  73. ------------------------------------------------------------------------------
  74. Paul Hatcher            PHONE    +44 904 432771
  75. Department of Computer Science    JANET    paulh@uk.ac.york.minster
  76. University of York        INTERNET paulh@minster.york.ac.uk
  77. Heslington, York, Y01 5DD    UUCP     {mcsun,uknet}!minster!paulh
  78.