From: ghosh-bhaskar@CS.YALE.EDU (Bhaskar Ghosh)
Subject: parallel graph partitioning: summary of references
Apparently-To: comp-parallel@uunet.uu.net
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
Date: Wed, 15 Jul 1992 21:02:02 GMT

Here is a list of references culled from the responses
to my posting about parallel graph partitioning techniques. 

i also include references about graph partitioning for sequential
computation - since a lot of interesting work has been done in the
area (Kernighan-Lin like heuristic-based approach, theory of
separators, simulated annealing) and one needs to be be familiar with
it to partition graphs in parallel.

Graph partitioning for parallel computation and parallel
graph partitioning are two overlapping areas - I have found very
little work done in the 2nd area. The problem we are thinking about
needs both - we need to divide up a dynamically changing non-uniform
grid quickly (in parallel) and get parallel processors to work on
independent pieces. 

Thanks to all the kind folks who responded and i hope the summary is 
of help to all interested.  The references are divided according to 
the responses, not according to any topic or theme. 

- bhaskar.

======================================================================
@article{DonathHoffman,
         author = {William E. Donath and A. J. Hoffman},
         title = {Lower Bounds for the Partitioning of Graphs},
         journal = {{IBM} Journal of Research and Development},
         volume = 17,
         year = 1973,
         pages = {420--425}
}

@phdthesis{Macgregor,
         author = {Robert M. MacGregor},
         title = {On Partitioning a Graph: A Theoretical and Empirical Study},
         school = {University of California at Berkeley},
         note = {UCB/ERL memorandum M78/14},
         year = 1978
}

@phdthesis{Bui,
         author = {Thang N. Bui},
         title = {Graph Bisection Algorithms},
         school = {Massachussetts Institute of Technology},
         year = 1986
}

@inproceedings{AwerbuchPeleg,
         author = {Baruch Awerbuch and David Peleg},
         title = {Sparse Partitions},
         booktitle = {Proceedings of the 31$^{st}$ {IEEE} Symposium on the
                    Foundations of Computer Science},
         year = 1990,
         pages = {503--513}
}

@inproceedings{AlonSeymourThomas,
         author = {Noga Alon and P. Seymour and R. Thomas},
         title = {A Separator Theorem for Graphs with an Excluded Minor
                  and its Applications},
         booktitle = {Proceedings of the 22$^{nd}$ {ACM} Symposium on Theory
                    of Computing},
         year = 1990,
         pages = {293--299}
}
 
@article{BhattLeighton,
         author = {Sandeep N. Bhatt and F. Thomas Leighton},
         title = {A Framework for Solving {VLSI} Graph Layout Problems},
         journal = JCSS,
         volume = 28,
         year = 1987,
         pages = {300--343}
}

@inproceedings{BuiChaudhuriLeightonSipser,
         author = {Thang N. Bui and Soma Chaudhuri and F. Thomas Leighton
                   and Michael Sipser},
         title = {Graph Bisection Algorithms with Good Average Case Behavior},
         booktitle = {Proceedings of the 25$^{th}$ {IEEE} Symposium on the
                    Foundations of Computer Science},
         year = 1984,
         pages = {181--192}
}

@inproceedings{FiducciaMattheyses,
         author = {Charles M. Fiduccia and R. M. Mattheyses},
         title = {A Linear-Time Heuristic for Improving Network Partitions},
         booktitle = {Proceedings of the 19$^{th}$ {IEEE} Design Automation
                      Conference},
         year = 1982,
         pages = {175--181}
}

@article{JohnsonAragonMcgeochSchevonI,
         author = {David S. Johnson and Cecilia R. Aragon
                   and Lyle A. McGeoch and Catherine Schevon},
         title = {Optimization by Simulated Annealing;
                  Part {I}, Graph Partitioning},
         journal = {Operations Research},
         volume = 37,
         year = 1989,
         pages = {865--892}
}

@article{KernighanLin,
         author = {Brian W. Kernighan and S. Lin},
         title = {An Efficient Heuristic Procedure for Partitioning Graphs},
         journal = {Bell System Technical Journal},
         volume = 49,
         year = 1970,
         pages = {291--307}
}

@article{Krishnamurthy,
         author = {Balakrishnan Krishnamurthy},
         title = {An Improved Min-Cut Algorithm for Partitioning
                  {VLSI} Networks},
         journal = IEEETC,
         volume = {C--33},
         year = 1984,
         pages = {438--446}
}

@inproceedings{LeightonRao,
         author = {F. Thomas Leighton and Satish Rao},
         title = {An Approximate Max-Flow Min-Cut Theorem for Uniform
                  Multicommodity Flow Problems with Applications to
                  Approximation Algorithms},
         booktitle = {Proceedings of the 29$^{th}$ {IEEE} Symposium on the
                    Foundations of Computer Science},
         year = 1988,
         pages = {422--431}
}

@article{LiptonTarjanApp,
         author = {Richard J. Lipton and Robert E. Tarjan},
         title = {Applications of a Planar Separator Theorem},
         journal = {SIAM Journal of Computing},
         volume = 9,
         year = 1980,
         pages = {615--627}
}

@article{Liu,
         author = {Joseph W. H. Liu},
         title = {Modification of the Minimum-Degree Algorithm by
                  Multiple Elimination},
         journal = {ACM Transactions on Mathematical Software},
         volume = 11,
         year = 1985,
         pages = {141--153}
}

@inproceedings{MillerThurston,
         author = {Gary L. Miller and W. Thurston},
         title = {Separators in Two and Three Dimensions},
         booktitle = {Proceedings of the 22$^{nd}$ {ACM} Symposium on Theory
                    of Computing},
         year = 1990,
         pages = {300--309}
}

@article{Plaisted,
         author = {David A. Plaisted},
         title = {A Heuristic Algorithm for Small Separators
                  in Arbitrary Graphs},
         journal = SIAMJC,
         volume = 19,
         year = 1990,
         pages = {267--280}
}
======================================================================

	article{savage,
	    author =        "J. Savage and M. G. Wloka",
	    title =         "Parallelism in Graph-Partitioning",
	    journal =       "Journal of Parallel and Distributed Computing",
	    year =          "1991",
	    month =         "November",
	    volume =        "13",
	    number =        "3",
	    pages =         "257-272",
	 }

%A M. G. Wloka
%T Parallel VLSI Synthesis
%R Ph.D. Thesis, Report No. CS-91-35
%I Department of Computer Science, Brown University, RI
%D 1991

======================================================================
"Implementation of Parallel Branch-and-Bound Algorithms -
Experiences with the Graph Partitioning Problem" 
by Jens Clausen and Jesper Larsson Traff.
Report number 89/16

"Parallel Graph Partitioning using Branch-and-Bound with Dynamic
Distribution of Sub-Problems"
by Jens Clausen and Jesper Larsson Traff.
Report Number 88/13

These are both technical reports from the Institute of Datalogy, at
the University of Copenhagen. On of these (the top one I think) was
also published in a recent edition of the "Annals of OR" journal, I do
not have the date, but I would guess around January 1992.

The 88 paper is a general discussion of the machine, algorithm etc
with some results while the 89 one compares the performance of two
different algorithms for solving the graph partitioning problem.
======================================================================

%A J. R. Banavar
%A D. Sherrington
%A N. Sourlas
%T Graph Partitioning and Statistical Mechanics
%D |JUL| 1986
%J J. Phys. A.
%R preprint
 
%A T. N. Bui
%T On Bisecting Random Graphs
%I |MIT|
%R MS Thesis MIT/LCS/TR-287
%D |FEB| 1983
 
%A T. Bui
%A C. Heigham
%A C. Jones
%A T. Leighton
%T Improving the Performance of the Kernighan-Lin and 
Simulated Annealing Graph Bisection Algorithms
%J 26th |DAC|
%I ACM/IEEE
%D 1989
%P 775-778
 
%A J. R. Gilbert
%A E. Zmijewski
%T A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor
%J Supercomputing: 1st International Conference
%D |JUN| 1987
%I Springer Verlag
%P 499-513
 
%A J. R. Gilbert
%A E. Zmijewski
%T A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor
%J International Journal of Parallel Programming
%V 16
%N 6
%P 427-449
%D 1987
 
%A A. Kahng
%T Fast Hypergraph Partition
%J 26th |DAC|
%D 1989
%P 762-766
 
%A B. Krishnamurthy
%T Constructing Test Cases for Partitioning Heuristics
%J|IEETC4|
%D |SEP| 1987
%V C-36
%N 9
%P 1112-1114
 
%A J. W. H. Liu
%T A Graph Partitioning Algorithm by Node Separators
%J ACM Transactions on Mathematical Software
%V 15
%N 3
%D |SEP| 1989
%P 198-219
 
%A A. Pothen
%A H. D. Simon
%A K.-P. Liou
%T Partitioning Sparse Matrices with Eigenvectors of Graphs
%J Siam J. Matrix Anal. Appl.
%V 11
%N 3
%P 430-452
%D |JUL| 1990
 
%A R. Sarnath 
%T A P-complete Graph Partition Problem
%D 1990
%R preprint
 
%A H. D. Simon
%T Partitioning of Unstructured Problems for Parallel Processing
%I NASA Ames Research Center
%R Report RNR-91-008
%D |FEB| 1991
 
%A G. Vijayan
%T Partitioning Logic to Optimize Routability on Graph Structures
%J IEEE something
%D 1990
%P 2638-2641


%A T. Leighton
%A S. Rao
%T An Approximate  Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow
   Problems With Application to Approximation Algorithms
%J 29th |FOCS|
%D 1988
%P 422-431
 
%A A. E. Dunlop
%A B. W. Kernighan
%T A Procedure for Placement of Standard-Cell VLSI Circuits
%J |IEETCAD|
%D |JAN| 1985
%V CAD-4
%N 1
%P 92-98
 
%A C. M. Fiduccia
%A R. M. Mattheyses
%T A Linear-Time Heuristic for Improving Network Partitions
%J 19th |DAC|
%D 1982
%P 175-181
%K kernigham graph local search
 
%A D. S. Johnson
%A C. H. Papadimitriou
%A M. Yannakakis
%T How Easy is Local Search?
%D 1985
%P 39-42
%J 26th |FOCS|
%K abstract complete kernigham graph partition
 
%A D. S. Johnson
%A C. H. Papadimitriou
%A M. Yannakakis
%T How Easy is Local Search?
%D 1988
%N 37
%P 79-100
%J Journal of Computer and Systems Sciences

%A R. D. Chamberlain
%A M. N. Edelman
%A M. A. Franklin
%A E. E. Witte
%T Simulated Annealing on a Multiprocessor
%J Proceedings of the International Conference on Computer Design
%D 1988
%P 540-544
 
%A F. Darema
%A S. Kirkpatrick
%A V. A. Norton
%T Parallel Algorithms for Chip Placement by Simulated Annealing
%D |MAY| 1987
%J IBM Journal of Research and Development
%P 391-401
%V 31
%N 3
%K One of the first important papers in the area.  Contains experimental
%K results on a parallel machine (simulated on a IBM 370)
 
%A D. R. Greening
%T A Taxonomy of Parallel Simulated Annealing Techniques
%I IBM
%R Technical Report No. RC 14884
%D 1989
%K A survey of work in the field.  Very complete bibliography.
 
%A S. Kirkpatrick
%T Optimization by Simulated Annealing: Quantitative Studies
%J J. Statistical Physics
%V 34
%P 975-986
%D 1984
%K placement
 
%A S. Kirkpatrick
%A C. D. Gelatt
%A M. P. Vecchi
%T Optimization by Simulated Annealing
%J Science
%D |MAY| 1983
%V 220
%N 4598
%P 671-680
%K placement
 
%A P. Roussel-Ragot
%A G. Dreyfus
%T A Problem Independent Parallel Implementation of Simulated Annealing: Models and Experiments
%J |IEETCAD|
%V 9
%N 8
%D |AUG| 1990
%P 827-835

======================================================================

Here is one reference:
    P. Sadayappan, F. Ercal, and J. Ramanujam, ``Parallel Graph 
Partitioning on a Hypercube,'' {\em Proc. of Fourth Conf. on Hypercube 
Concurrent Comp. and Appl.}, pp. 67-70, March, 1989.

======================================================================


 E-G.TALBI, P.BESSIERE
 "A Parallel Genetic Algorithm for the Graph Partitioning Problem"
 ACM Int. Conf. on Supercomputing
 cologne, Germany, July 1991.


======================================================================

Ravikumar, Sastry and Patnaik, "Parallel Ckt Part. on a reduced array
architecture", Computer-Aided Design, vol 21, sept 1989 pp 447-455

"On Parallelizing Graph-Partitioning Heuristics", not sure what conf.
it was, but it is one of the LNCS's: number 443  (pp 476-489)

======================================================================

	Muehlenbein, Gorges-Schleuter, Kraemer: New solutions to the
	  mapping problem of parallel systems: The evolution approach
	Parallel Computing 4 (1987), pp. 269-279

======================================================================
-- 
===============================================================================
Bhaskar Ghosh   	    		"Tomar pujar chholey, 
ghosh@cs.yale.edu  @yalecs.bitnet        Tomay bhulei thaki"- Robithakur
===============================================================================

Newsgroups: comp.parallel