Schaudt, Oliver and Schrader, Rainer (2012). The complexity of connected dominating sets and total dominating sets with specified induced subgraphs. Inf. Process. Lett., 112 (24). S. 953 - 958. AMSTERDAM: ELSEVIER. ISSN 1872-6119
Full text not available from this repository.Abstract
Given a graph class g, it is natural to ask (i) whether a given graph G has a connected or a total dominating set whose induced subgraph is a member of g and (ii) whether G has such a set of cardinality at most a given threshold. We give sufficient conditions on g under which these two problems are NP-hard. This condition is fulfilled in a wide variety of classes of graphs. (C) 2012 Elsevier B.V. All rights reserved.
| Item Type: | Journal Article | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-476400 | ||||||||||||
| DOI: | 10.1016/j.ipl.2012.09.002 | ||||||||||||
| Journal or Publication Title: | Inf. Process. Lett. | ||||||||||||
| Volume: | 112 | ||||||||||||
| Number: | 24 | ||||||||||||
| Page Range: | S. 953 - 958 | ||||||||||||
| Date: | 2012 | ||||||||||||
| Publisher: | ELSEVIER | ||||||||||||
| Place of Publication: | AMSTERDAM | ||||||||||||
| ISSN: | 1872-6119 | ||||||||||||
| Language: | English | ||||||||||||
| Faculty: | Unspecified | ||||||||||||
| Divisions: | Unspecified | ||||||||||||
| Subjects: | no entry | ||||||||||||
| Uncontrolled Keywords: |
|
||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/47640 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
 |
View Item |