An O(n1.5logn) 1-d compaction algorithm
Chi-Yuan Lo, Ravi Varadarajan · 1990
In this paper, we bound the complexity of the major algorithms of 1-d compaction in graph solution and module assembly to be Ο(n15logn). An 1-d hierarchical module assembly method is shown to be free from the x-y interlock problem and achieves significant improvement in space and time requirements by exploiting hierarchy.