On stable cutsets in graphs

Authors
Brandstadt, A Dragan, FF Le, VB Szymczak, T
Citation
A. Brandstadt et al., On stable cutsets in graphs, DISCR APP M, 105(1-3), 2000, pp. 39-50
Citations number
20
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE APPLIED MATHEMATICS → ACNP
Volume
105
Issue
1-3
Year of publication
2000
Pages
39 - 50
Database
ISI
SICI code
Abstract
We answer a question of Corneil and Fonlupt by showing that deciding whethe r a graph has a stable cutset is NP-complete even fcr restricted graph clas ses. Some efficiently solvable cases will he discussed, too. (C) 2000 Elsev ier Science B.V. All rights reserved.