T. Ito
On disconnected cuts and separators
Ito, T.; Kaminski, M.; Paulusma, D.; Thilikos, D.M.
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.
Citation
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027
Journal Article Type | Article |
---|---|
Publication Date | Aug 1, 2011 |
Deposit Date | Dec 6, 2011 |
Journal | Discrete Applied Mathematics |
Print ISSN | 0166-218X |
Electronic ISSN | 1872-6771 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 159 |
Issue | 13 |
Pages | 1345-1351 |
DOI | https://doi.org/10.1016/j.dam.2011.04.027 |
Keywords | Cut set, 2K2-partition, Retraction, Compaction. |
Public URL | https://durham-repository.worktribe.com/output/1533525 |
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Matching cuts in graphs of high girth and H-free graphs
(2023)
Presentation / Conference Contribution
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search