A Polylogarithmic Approximation of the Minimum Bisection
2006; Society for Industrial and Applied Mathematics; Volume: 48; Issue: 1 Linguagem: Inglês
10.1137/050640904
ISSN1095-7200
AutoresRobert Krauthgamer, Uriel Feige,
Tópico(s)Advanced Graph Theory Research
ResumoA 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(\log^{1.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 $\sqrt{n}$.
Referência(s)