Schaudt, Oliver and Schrader, Rainer
(2010).
The complexity of connected domination and total domination by restricted induced graphs.
Working Paper.
|
PDF
zaik2010-606.pdf Download (208kB) | Preview |
Abstract
Given a graph class C, it is natural to ask whether a given graph has a connected or a total dominating set inducing a graph of C and, if so, what is the minimal size of such a set. We give a sufficient condition on C for the intractability of this problem. This condition is fulfilled by a wide range of graph classes.
| Item Type: | Preprints, Working Papers or Reports (Working Paper) | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-550009 | ||||||||||||
| Journal or Publication Title: | Journal of Discrete Algorithms | ||||||||||||
| Date: | 2010 | ||||||||||||
| Language: | English | ||||||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||
| Subjects: | Data processing Computer science | ||||||||||||
| Refereed: | No | ||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/55000 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |