Algorithms for Graph Partitioning: A Survey

• 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 thatthe union set of  Ni  where  i = 1...p  equals  N  and  Ni  is disjoint from  Nj  for  i =/ j  , 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,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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

rap (ämneskategori)