We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Minimal disconnected cuts in planar graphs.
- Authors
Kamiński, Marcin; Paulusma, Daniël; Stewart, Anthony; Thilikos, Dimitrios M.
- Abstract
The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar graphs. We show that it is polynomial-time solvable on 3-connected planar graphs but NP-hard for 2-connected planar graphs. Our technique for the first result is based on a structural characterization of minimal disconnected cuts in 3-connected
- Subjects
PLANAR graphs; GRAPH theory
- Publication
Networks, 2016, Vol 68, Issue 4, p250
- ISSN
0028-3045
- Publication type
Article
- DOI
10.1002/net.21696