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
N_{1}
,
N_{2}
,...
N_{p}
of
N
such that
 the union set of
N_{i}
where
i = 1...p
equals
N
and
N_{i}
is disjoint from
N_{j}
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
N_{i}
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 stateoftheart of sequential and parallel graph
partitioning problems. 