FAST APPROXIMATION ALGORITHMS ON MAXCUT, K-COLORING, AND K-COLOR ORDERING FOR VLSI APPLICATIONS

There are a number of VLSI problems that have a common structure. We i nvestigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via mi nimization. Along the line, we first propose a linear-time approximati on algorithm on maxcut and two closely related problems. k-coloring an d maximal k-color ordering problem. The k-coloring is a generalization of the maxcut and the maximal k-color ordering is a generalization of the k-coloring. For a graph G with e edges and n vertices, our maxcut approximation algorithm runs in O(e + n) sequential time yielding a n ode-balanced maxcut with size at least (w(E) + w(E)/n)/2, improving th e time complexity of O(e log e) known before. Building on the proposed maxcut technique and employing a height-balanced binary decomposition , we devise an O((e + n)log k) time algorithm for the k-coloring probl em which always finds a k-partition of vertices such that the number o f bad (or ''defected'') edges does not exceed (w(E)/k)((n - 1)/n)(log k), thus improving both the time complexity O(enk) and the bound e/k k nown before. The other related problem is the maximal k-color ordering problem that has been an open problem [16]. We show the problem is NP -complete, then present an approximation algorithm building on our k-c oloring structure. A performance bound on maximal k-color ordering cos t, 2kw(E)/3 is attained in O(ek) time. The solution quality of this al gorithm is also tested experimentally and found to be effective.