The slicing-tree for an individual of the initial population is composed
in a bottom-up fashion.
A special heuristic - the iterated matching [2] - is used
to create building-blocks which define high quality partial layouts.
For that, a complete graph is constructed:
the nodes represent the blocks, and
each edge is weighted with a value which defines the quality of a meta-block consisting of the
two blocks characterized by the adjacent nodes.
A matching in this graph is a set of disjunct node pairs and the maximum weighted
matching is the matching with the maximal sum of edge weights (cf. fig. 4).
The quality of a meta-block is marked out by the number of common nets
of the combined blocks.
Figure 4: A matching graph for four blocks, the three possible matchings
and the maximum weighted matching (c)
The matching process is iterated for each level of the tree until the root node
is computed.
In the second iteration, meta-blocks which consist of two blocks are paired,
in the third iteration meta-blocks with four blocks are combined, and so on.
This heuristic places highly connected blocks together and so reduces the
overall wirelength and the total area of the layout.
Because the iterated matching is a deterministic process,
care has to be taken to create various individuals.
For that, randomness is included in the computation of the
edge weights for some of the used matching graphs.