home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / parallel / 1758 < prev    next >
Encoding:
Internet Message Format  |  1992-07-21  |  12.9 KB
  1. Xref: sparky comp.parallel:1758 comp.theory:1673
  2. Newsgroups: comp.parallel,comp.theory
  3. Path: sparky!uunet!gatech!hubcap!fpst
  4. From: ghosh-bhaskar@CS.YALE.EDU (Bhaskar Ghosh)
  5. Subject: parallel graph partitioning: summary of references
  6. Message-ID: <1992Jul21.143605.21628@hubcap.clemson.edu>
  7. Apparently-To: comp-parallel@uunet.uu.net
  8. Sender: news@CS.YALE.EDU (Usenet News)
  9. Nntp-Posting-Host: calvin.na.cs.yale.edu
  10. Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
  11. Date: Wed, 15 Jul 1992 21:02:02 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 440
  14.  
  15. Here is a list of references culled from the responses
  16. to my posting about parallel graph partitioning techniques. 
  17.  
  18. i also include references about graph partitioning for sequential
  19. computation - since a lot of interesting work has been done in the
  20. area (Kernighan-Lin like heuristic-based approach, theory of
  21. separators, simulated annealing) and one needs to be be familiar with
  22. it to partition graphs in parallel.
  23.  
  24. Graph partitioning for parallel computation and parallel
  25. graph partitioning are two overlapping areas - I have found very
  26. little work done in the 2nd area. The problem we are thinking about
  27. needs both - we need to divide up a dynamically changing non-uniform
  28. grid quickly (in parallel) and get parallel processors to work on
  29. independent pieces. 
  30.  
  31. Thanks to all the kind folks who responded and i hope the summary is 
  32. of help to all interested.  The references are divided according to 
  33. the responses, not according to any topic or theme. 
  34.  
  35. - bhaskar.
  36.  
  37. ======================================================================
  38. @article{DonathHoffman,
  39.          author = {William E. Donath and A. J. Hoffman},
  40.          title = {Lower Bounds for the Partitioning of Graphs},
  41.          journal = {{IBM} Journal of Research and Development},
  42.          volume = 17,
  43.          year = 1973,
  44.          pages = {420--425}
  45. }
  46.  
  47. @phdthesis{Macgregor,
  48.          author = {Robert M. MacGregor},
  49.          title = {On Partitioning a Graph: A Theoretical and Empirical Study},
  50.          school = {University of California at Berkeley},
  51.          note = {UCB/ERL memorandum M78/14},
  52.          year = 1978
  53. }
  54.  
  55. @phdthesis{Bui,
  56.          author = {Thang N. Bui},
  57.          title = {Graph Bisection Algorithms},
  58.          school = {Massachussetts Institute of Technology},
  59.          year = 1986
  60. }
  61.  
  62. @inproceedings{AwerbuchPeleg,
  63.          author = {Baruch Awerbuch and David Peleg},
  64.          title = {Sparse Partitions},
  65.          booktitle = {Proceedings of the 31$^{st}$ {IEEE} Symposium on the
  66.                     Foundations of Computer Science},
  67.          year = 1990,
  68.          pages = {503--513}
  69. }
  70.  
  71. @inproceedings{AlonSeymourThomas,
  72.          author = {Noga Alon and P. Seymour and R. Thomas},
  73.          title = {A Separator Theorem for Graphs with an Excluded Minor
  74.                   and its Applications},
  75.          booktitle = {Proceedings of the 22$^{nd}$ {ACM} Symposium on Theory
  76.                     of Computing},
  77.          year = 1990,
  78.          pages = {293--299}
  79. }
  80.  
  81. @article{BhattLeighton,
  82.          author = {Sandeep N. Bhatt and F. Thomas Leighton},
  83.          title = {A Framework for Solving {VLSI} Graph Layout Problems},
  84.          journal = JCSS,
  85.          volume = 28,
  86.          year = 1987,
  87.          pages = {300--343}
  88. }
  89.  
  90. @inproceedings{BuiChaudhuriLeightonSipser,
  91.          author = {Thang N. Bui and Soma Chaudhuri and F. Thomas Leighton
  92.                    and Michael Sipser},
  93.          title = {Graph Bisection Algorithms with Good Average Case Behavior},
  94.          booktitle = {Proceedings of the 25$^{th}$ {IEEE} Symposium on the
  95.                     Foundations of Computer Science},
  96.          year = 1984,
  97.          pages = {181--192}
  98. }
  99.  
  100. @inproceedings{FiducciaMattheyses,
  101.          author = {Charles M. Fiduccia and R. M. Mattheyses},
  102.          title = {A Linear-Time Heuristic for Improving Network Partitions},
  103.          booktitle = {Proceedings of the 19$^{th}$ {IEEE} Design Automation
  104.                       Conference},
  105.          year = 1982,
  106.          pages = {175--181}
  107. }
  108.  
  109. @article{JohnsonAragonMcgeochSchevonI,
  110.          author = {David S. Johnson and Cecilia R. Aragon
  111.                    and Lyle A. McGeoch and Catherine Schevon},
  112.          title = {Optimization by Simulated Annealing;
  113.                   Part {I}, Graph Partitioning},
  114.          journal = {Operations Research},
  115.          volume = 37,
  116.          year = 1989,
  117.          pages = {865--892}
  118. }
  119.  
  120. @article{KernighanLin,
  121.          author = {Brian W. Kernighan and S. Lin},
  122.          title = {An Efficient Heuristic Procedure for Partitioning Graphs},
  123.          journal = {Bell System Technical Journal},
  124.          volume = 49,
  125.          year = 1970,
  126.          pages = {291--307}
  127. }
  128.  
  129. @article{Krishnamurthy,
  130.          author = {Balakrishnan Krishnamurthy},
  131.          title = {An Improved Min-Cut Algorithm for Partitioning
  132.                   {VLSI} Networks},
  133.          journal = IEEETC,
  134.          volume = {C--33},
  135.          year = 1984,
  136.          pages = {438--446}
  137. }
  138.  
  139. @inproceedings{LeightonRao,
  140.          author = {F. Thomas Leighton and Satish Rao},
  141.          title = {An Approximate Max-Flow Min-Cut Theorem for Uniform
  142.                   Multicommodity Flow Problems with Applications to
  143.                   Approximation Algorithms},
  144.          booktitle = {Proceedings of the 29$^{th}$ {IEEE} Symposium on the
  145.                     Foundations of Computer Science},
  146.          year = 1988,
  147.          pages = {422--431}
  148. }
  149.  
  150. @article{LiptonTarjanApp,
  151.          author = {Richard J. Lipton and Robert E. Tarjan},
  152.          title = {Applications of a Planar Separator Theorem},
  153.          journal = {SIAM Journal of Computing},
  154.          volume = 9,
  155.          year = 1980,
  156.          pages = {615--627}
  157. }
  158.  
  159. @article{Liu,
  160.          author = {Joseph W. H. Liu},
  161.          title = {Modification of the Minimum-Degree Algorithm by
  162.                   Multiple Elimination},
  163.          journal = {ACM Transactions on Mathematical Software},
  164.          volume = 11,
  165.          year = 1985,
  166.          pages = {141--153}
  167. }
  168.  
  169. @inproceedings{MillerThurston,
  170.          author = {Gary L. Miller and W. Thurston},
  171.          title = {Separators in Two and Three Dimensions},
  172.          booktitle = {Proceedings of the 22$^{nd}$ {ACM} Symposium on Theory
  173.                     of Computing},
  174.          year = 1990,
  175.          pages = {300--309}
  176. }
  177.  
  178. @article{Plaisted,
  179.          author = {David A. Plaisted},
  180.          title = {A Heuristic Algorithm for Small Separators
  181.                   in Arbitrary Graphs},
  182.          journal = SIAMJC,
  183.          volume = 19,
  184.          year = 1990,
  185.          pages = {267--280}
  186. }
  187. ======================================================================
  188.  
  189.     article{savage,
  190.         author =        "J. Savage and M. G. Wloka",
  191.         title =         "Parallelism in Graph-Partitioning",
  192.         journal =       "Journal of Parallel and Distributed Computing",
  193.         year =          "1991",
  194.         month =         "November",
  195.         volume =        "13",
  196.         number =        "3",
  197.         pages =         "257-272",
  198.      }
  199.  
  200. %A M. G. Wloka
  201. %T Parallel VLSI Synthesis
  202. %R Ph.D. Thesis, Report No. CS-91-35
  203. %I Department of Computer Science, Brown University, RI
  204. %D 1991
  205.  
  206. ======================================================================
  207. "Implementation of Parallel Branch-and-Bound Algorithms -
  208. Experiences with the Graph Partitioning Problem" 
  209. by Jens Clausen and Jesper Larsson Traff.
  210. Report number 89/16
  211.  
  212. "Parallel Graph Partitioning using Branch-and-Bound with Dynamic
  213. Distribution of Sub-Problems"
  214. by Jens Clausen and Jesper Larsson Traff.
  215. Report Number 88/13
  216.  
  217. These are both technical reports from the Institute of Datalogy, at
  218. the University of Copenhagen. On of these (the top one I think) was
  219. also published in a recent edition of the "Annals of OR" journal, I do
  220. not have the date, but I would guess around January 1992.
  221.  
  222. The 88 paper is a general discussion of the machine, algorithm etc
  223. with some results while the 89 one compares the performance of two
  224. different algorithms for solving the graph partitioning problem.
  225. ======================================================================
  226.  
  227. %A J. R. Banavar
  228. %A D. Sherrington
  229. %A N. Sourlas
  230. %T Graph Partitioning and Statistical Mechanics
  231. %D |JUL| 1986
  232. %J J. Phys. A.
  233. %R preprint
  234.  
  235. %A T. N. Bui
  236. %T On Bisecting Random Graphs
  237. %I |MIT|
  238. %R MS Thesis MIT/LCS/TR-287
  239. %D |FEB| 1983
  240.  
  241. %A T. Bui
  242. %A C. Heigham
  243. %A C. Jones
  244. %A T. Leighton
  245. %T Improving the Performance of the Kernighan-Lin and 
  246. Simulated Annealing Graph Bisection Algorithms
  247. %J 26th |DAC|
  248. %I ACM/IEEE
  249. %D 1989
  250. %P 775-778
  251.  
  252. %A J. R. Gilbert
  253. %A E. Zmijewski
  254. %T A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor
  255. %J Supercomputing: 1st International Conference
  256. %D |JUN| 1987
  257. %I Springer Verlag
  258. %P 499-513
  259.  
  260. %A J. R. Gilbert
  261. %A E. Zmijewski
  262. %T A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor
  263. %J International Journal of Parallel Programming
  264. %V 16
  265. %N 6
  266. %P 427-449
  267. %D 1987
  268.  
  269. %A A. Kahng
  270. %T Fast Hypergraph Partition
  271. %J 26th |DAC|
  272. %D 1989
  273. %P 762-766
  274.  
  275. %A B. Krishnamurthy
  276. %T Constructing Test Cases for Partitioning Heuristics
  277. %J|IEETC4|
  278. %D |SEP| 1987
  279. %V C-36
  280. %N 9
  281. %P 1112-1114
  282.  
  283. %A J. W. H. Liu
  284. %T A Graph Partitioning Algorithm by Node Separators
  285. %J ACM Transactions on Mathematical Software
  286. %V 15
  287. %N 3
  288. %D |SEP| 1989
  289. %P 198-219
  290.  
  291. %A A. Pothen
  292. %A H. D. Simon
  293. %A K.-P. Liou
  294. %T Partitioning Sparse Matrices with Eigenvectors of Graphs
  295. %J Siam J. Matrix Anal. Appl.
  296. %V 11
  297. %N 3
  298. %P 430-452
  299. %D |JUL| 1990
  300.  
  301. %A R. Sarnath 
  302. %T A P-complete Graph Partition Problem
  303. %D 1990
  304. %R preprint
  305.  
  306. %A H. D. Simon
  307. %T Partitioning of Unstructured Problems for Parallel Processing
  308. %I NASA Ames Research Center
  309. %R Report RNR-91-008
  310. %D |FEB| 1991
  311.  
  312. %A G. Vijayan
  313. %T Partitioning Logic to Optimize Routability on Graph Structures
  314. %J IEEE something
  315. %D 1990
  316. %P 2638-2641
  317.  
  318.  
  319. %A T. Leighton
  320. %A S. Rao
  321. %T An Approximate  Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow
  322.    Problems With Application to Approximation Algorithms
  323. %J 29th |FOCS|
  324. %D 1988
  325. %P 422-431
  326.  
  327. %A A. E. Dunlop
  328. %A B. W. Kernighan
  329. %T A Procedure for Placement of Standard-Cell VLSI Circuits
  330. %J |IEETCAD|
  331. %D |JAN| 1985
  332. %V CAD-4
  333. %N 1
  334. %P 92-98
  335.  
  336. %A C. M. Fiduccia
  337. %A R. M. Mattheyses
  338. %T A Linear-Time Heuristic for Improving Network Partitions
  339. %J 19th |DAC|
  340. %D 1982
  341. %P 175-181
  342. %K kernigham graph local search
  343.  
  344. %A D. S. Johnson
  345. %A C. H. Papadimitriou
  346. %A M. Yannakakis
  347. %T How Easy is Local Search?
  348. %D 1985
  349. %P 39-42
  350. %J 26th |FOCS|
  351. %K abstract complete kernigham graph partition
  352.  
  353. %A D. S. Johnson
  354. %A C. H. Papadimitriou
  355. %A M. Yannakakis
  356. %T How Easy is Local Search?
  357. %D 1988
  358. %N 37
  359. %P 79-100
  360. %J Journal of Computer and Systems Sciences
  361.  
  362. %A R. D. Chamberlain
  363. %A M. N. Edelman
  364. %A M. A. Franklin
  365. %A E. E. Witte
  366. %T Simulated Annealing on a Multiprocessor
  367. %J Proceedings of the International Conference on Computer Design
  368. %D 1988
  369. %P 540-544
  370.  
  371. %A F. Darema
  372. %A S. Kirkpatrick
  373. %A V. A. Norton
  374. %T Parallel Algorithms for Chip Placement by Simulated Annealing
  375. %D |MAY| 1987
  376. %J IBM Journal of Research and Development
  377. %P 391-401
  378. %V 31
  379. %N 3
  380. %K One of the first important papers in the area.  Contains experimental
  381. %K results on a parallel machine (simulated on a IBM 370)
  382.  
  383. %A D. R. Greening
  384. %T A Taxonomy of Parallel Simulated Annealing Techniques
  385. %I IBM
  386. %R Technical Report No. RC 14884
  387. %D 1989
  388. %K A survey of work in the field.  Very complete bibliography.
  389.  
  390. %A S. Kirkpatrick
  391. %T Optimization by Simulated Annealing: Quantitative Studies
  392. %J J. Statistical Physics
  393. %V 34
  394. %P 975-986
  395. %D 1984
  396. %K placement
  397.  
  398. %A S. Kirkpatrick
  399. %A C. D. Gelatt
  400. %A M. P. Vecchi
  401. %T Optimization by Simulated Annealing
  402. %J Science
  403. %D |MAY| 1983
  404. %V 220
  405. %N 4598
  406. %P 671-680
  407. %K placement
  408.  
  409. %A P. Roussel-Ragot
  410. %A G. Dreyfus
  411. %T A Problem Independent Parallel Implementation of Simulated Annealing: Models and Experiments
  412. %J |IEETCAD|
  413. %V 9
  414. %N 8
  415. %D |AUG| 1990
  416. %P 827-835
  417.  
  418. ======================================================================
  419.  
  420. Here is one reference:
  421.     P. Sadayappan, F. Ercal, and J. Ramanujam, ``Parallel Graph 
  422. Partitioning on a Hypercube,'' {\em Proc. of Fourth Conf. on Hypercube 
  423. Concurrent Comp. and Appl.}, pp. 67-70, March, 1989.
  424.  
  425. ======================================================================
  426.  
  427.  
  428.  E-G.TALBI, P.BESSIERE
  429.  "A Parallel Genetic Algorithm for the Graph Partitioning Problem"
  430.  ACM Int. Conf. on Supercomputing
  431.  cologne, Germany, July 1991.
  432.  
  433.  
  434. ======================================================================
  435.  
  436. Ravikumar, Sastry and Patnaik, "Parallel Ckt Part. on a reduced array
  437. architecture", Computer-Aided Design, vol 21, sept 1989 pp 447-455
  438.  
  439. "On Parallelizing Graph-Partitioning Heuristics", not sure what conf.
  440. it was, but it is one of the LNCS's: number 443  (pp 476-489)
  441.  
  442. ======================================================================
  443.  
  444.     Muehlenbein, Gorges-Schleuter, Kraemer: New solutions to the
  445.       mapping problem of parallel systems: The evolution approach
  446.     Parallel Computing 4 (1987), pp. 269-279
  447.  
  448. ======================================================================
  449. -- 
  450. ===============================================================================
  451. Bhaskar Ghosh                   "Tomar pujar chholey, 
  452. ghosh@cs.yale.edu  @yalecs.bitnet        Tomay bhulei thaki"- Robithakur
  453. ===============================================================================
  454.  
  455.