An O(n sup 1.5 logn) 1d Compaction Algorithm.

In this paper, we bound the complexity of the major algorithms of 1-d compaction in graph solution and module assembly to be O(n sup 1.5 logn). An 1-d hierarchical module assembly method is shown to be free from the x-y interlock problem and to have the monotonically non-increasing property in area.