Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for VLSI applications

Abstract

There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimization. Along the line, we first propose a linear-time approximation algorithm on maxcut and two closely related problems: k-coloring and 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 nodebalanced maxcut with size at least (w(E)+w(E)/n)/2, improving the 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 problem which always finds a k-partition of vertices such that the number of bad (or "defected") edges does not exceed (w(E)/k)((n-1)/n)/sup log k/, thus improving both the time complexity O(enk) and the bound e/k known before. The other related problem is the maximal k-color ordering problem that has been an open problem. We show the problem is NP-complete, then present an approximation algorithm building on our k-coloring structure. A performance bound on maximal k-color ordering cost, 2kw(E)/3 is attained in O(ek) time. The solution quality of this algorithm is also tested experimentally and found to be effective.