Homework 2. Partitioning (Due 2/5/2009):
1. Fiduccia-Mattheyses Method takes time
O(pxbmax) for each pass, where p is #terminals
and bmax is the maximum cost of a hyperedge.
Revise the method and update the complexity
when the cost of the hyperedges is not integer.
2. List five different partitioning formulations
and indicate which problems are NP-complete.
3. Given a netlist (shown in the class), derive
the eigenvector which corresponds to the second
smallest eigenvalue.
4. Given a netlist in problem 3, derive the
resistance between all pairs of nodes.
5. State and prove the relation between the
max-flow min-cut and linear placement.