Complexity and approximability of the k‐way vertex cut
2014
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. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 170–178 2014
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
34
References
14
Citations
NaN
KQI