Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

On disconnected cuts and separators.

Ito, T. and Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (2011) 'On disconnected cuts and separators.', Discrete applied mathematics., 159 (13). pp. 1345-1351.

Abstract

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V∖U)∪{u} is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.

Item Type:Article
Keywords:Cut set, 2K2-partition, Retraction, Compaction.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2011.04.027
Record Created:07 Dec 2011 14:51
Last Modified:03 Apr 2013 16:20

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library