| The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout? (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. Given a graph G with weighted edges, and a subset of nodes T,theT-join problem asks for a minimum weight edgesetA such thata node u is incident to an odd number of edges of A i u 2 T.We describe the applications of the T-join problem in sparse graphs to the phase assignment problem in VLSI mask layout and to conformal re nement of nite element meshes. We suggest a practical algorithm for the T-join problem. In sparse graphs, this algorithm is faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithm. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||