Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
A bisection of a graph with n vertices is a partition of its vertices into two sets, each of size n/2. The bisection cost is the number of edges connecting the two sets. The problem of finding a bisection of minimum cost is prototypical to graph partitioning problems, which arise in numerous contexts. This problem is NP-hard. We present an algorithm that finds a bisection whose cost is within a factor of O(log1.5 n) from the minimum. For graphs excluding any fixed graph as a minor (e.g., planar graphs) we obtain an improved approximation ratio of O(log n). The previously known approximation ratio for bisection was roughly √n. © 2006 Society for Industrial and Applied Mathematics.
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Matthew A Grayson
Journal of Complexity
Naga Ayachitula, Melissa Buco, et al.
SCC 2007