Göm menyn
Files: Description Format
Fulltext PDF (requires Acrobat Reader)
Fulltext PostScript (requires a PostScript Reader)
   
Author: Per-Olof Fjällström
Article title: Algorithms for Graph Partitioning: A Survey
Publ. type: Article
Volume: 3
Article No: 10
Language: English
Abstract [en]: The graph partitioning problem is as follows.
  Given a graph  G =  (N, E)   (where  N  is a set of weighted nodes and  E  is a set of weighted edges) and a positive integer  p  , find  p  subsets  N1  ,  N2  ,...  Np  of  N  such that
  1. the union set of  Ni  where  i = 1...p  equals  N  and  Ni  is disjoint from  Nj  for  i =/ j  ,
  2.  W(i)~W/p  where  i = 1, 2...p  , where  W(i)  and  W  are the sums of the node weights in  Ni  and  N  , respectively,
  3. the cut size, i.e., the sum of the weights of edges crossing between subsets is minimized.
This problem is of interest in areas such as VLSI placement and routing, and efficient parallel implementations of finte element methods. In this survey we summarize the state-of-the-art of sequential and parallel graph partitioning problems.
Publisher: Linköping University Electronic Press
Year: 1998
Available: 1998-08-10
No. of pages: 34
Series: Linköping Electronic Articles in Computer and Information Science
ISSN: 1401-9841


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21