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
Physical Description:Online-Ressource
QR Code: Show QR Code