Graph Partitioning

Problem Search space is hugh:
- 2^V - 2 (for weighed nodes)
- reasoned by powerset
- V choose V/2 (for non-weighed nodes)


Partitioning is used to generate constraints for placement, as opposed to its original use for divide-and-conquer a problem. It's useful in placement where cells and wires are abstracted to nodes and edges. Delays are represented by weighs. The problem is formulated as partitioning a set of nodes into clusters of approx. equal size. The problem is known to be NP-complete. K&L's algorithm leverages heuristics to give good solutions.

Kernighan and Lin's algorithm:
Rely on gain calculation (for exchange a, b): g = Da - Db - 2*Cab, where Di = Ei (external cost) - Ii (internal cost). KL goes through a series of n exchanges, and chooses the culmulative gain maximum.
- O(n^2 log n)

Feduccia and Mattheyses
- claims O(n)


Multilevel scheme
1. Coarsening phase
2. Partitioning phase
3. Uncoarsening phase

- The main idea is that coarsening reduces the number of nodes and edges, which helps to speed up the partitioning alg.

- Collapsing vertexes into multinodes by matching
- Matching is not unique, so how do we find good matching?