Routing

Greedy Channel Router (Rivest and Fiduccia '82):
- problem definition (given channel length, list of T and B pins, and set of L and R nets).
- terms: pins, jog, track, collapse,
- heuristics: rising/falling/steady,

For each column:
1. bring in T and B nets
2. collapse split nets (prove it exponential)
3. reduce the range of split nets
4. raise or lower nets
5. widen channel to bring in new nets


The Path Connection Problem (Lee '61) - The "Lee's Algorithm"
- definition: (C, S, N, Gamma, M), F, and c*, c**
- basically BFS, using cell mass for path weight, and chain coordinates for backtracing

- Dijskra shortest path

Miminum Spanning Tree - useful for city road planning, or laying TV cables within an area.
- for any cut of the graph, the min edge across is part of MST

3D Circuit & 3D Routing
- for 2D, there are usually 6-7 layers

The "switchbox" problem is to solve the intersection of channel