@inproceedings{e60fffba46694b10a245d356474a1b60,
title = "How to cut a graph into many pieces",
abstract = "In this paper we consider the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of connected components. We present the picture of the computational complexity and the approximability of this problem for several natural classes of graphs. We first provide an overview of the hardness of approximation of this problem, which stems mainly from its close relation to the Independent Set and to the Maximum Clique problem. Next, we show that the problem is solvable in polynomial time for interval graphs and graphs of bounded treewidth. We also show that MaxiNum Components is fixed-parameter tractable on planar graphs with the size of the separator as the parameter. Our main contribution is the derivation of an efficient polynomial-time approximation scheme for the problem on planar graphs.",
author = "\{Zwaan, van der\}, G.R.J. and A. Berger and A. Grigoriev",
year = "2011",
doi = "10.1007/978-3-642-20877-5\_20",
language = "English",
isbn = "978-3-642-20876-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "184--194",
editor = "M. Ogihara and J. Tarui",
booktitle = "Theory and Applications of Models of Computation : 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings",
address = "Germany",
}