Matthew A Grayson
Journal of Complexity
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.
Matthew A Grayson
Journal of Complexity
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990