| 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
- the 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. |