Back to Search
Start Over
Parameterized Domination in Circle Graphs.
- Source :
- Theory of Computing Systems; Jan2014, Vol. 54 Issue 1, p45-72, 28p
- Publication Year :
- 2014
-
Abstract
- A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, ] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 54
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 93627332
- Full Text :
- https://doi.org/10.1007/s00224-013-9478-8