Abstract
In this article, we consider k-way vertex cut: the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of components. Our main contribution is the derivation of an efficient polynomial-time approximation scheme for the problem on planar graphs. Also, we show that k-way vertex cut is polynomially solvable on graphs of bounded treewidth and fixed-parameter tractable on planar graphs with the size of the separator as the parameter.
Original language | English |
---|---|
Pages (from-to) | 170-178 |
Number of pages | 9 |
Journal | Networks |
Volume | 63 |
Issue number | 2 |
DOIs | |
Publication status | Published - Mar 2014 |
Keywords
- planar graph
- separator
- connectivity
- computational complexity
- approximation scheme
- APPROXIMATION ALGORITHMS
- BOUNDED TREEWIDTH
- GRAPHS
- MULTICUT