Efficient algorithms for single- and two-layer linear placement of parallel graphs

✍ Scribed by S.C. Nandy; G.N. Nandakumar; B.B. Bhattacharya

• Book ID: 104353096
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 904 KB
• Volume: 34
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(97)00239-3

✦ Synopsis

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.