Parameterized complexity of critical node cuts

We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of par...

Full description

Bibliographic Details
Published in:Theoretical computer science : the journal of the EATCS, Vol. 651 (2016), p. 62-75
Main Author: Hermelin, Danny
Other Involved Persons: Kaspi, Moshe ; Komusiewicz, Christian ; Navon, Barak
Format: electronic Article
Language:English
Physical Description:Online-Ressource
DOI:10.1016/j.tcs.2016.08.018
QR Code: Show QR Code