@inproceedings{9f9a493bd89d4d4588e8bd28920e0bf9,
title = "On independence domination",
abstract = "Let G be a graph. The independence-domination number γi (G) is the maximum over all independent sets I in G of the minimal number of vertices needed to dominate I. In this paper we investigate the computational complexity of γi (G) for graphs in several graph classes related to cographs. We present an exact exponential algorithm. We show that there is a polynomial-time algorithm to compute a maximum independent set in the Cartesian product of two cographs. We prove that independence domination is NP-hard for planar graphs and we present a PTAS.",
keywords = "Cograph, Distance-hereditary graph, Domination, Exact algorithm, Independence domination, Permutation graph",
author = "Hon, {Wing Kai} and Ton Kloks and Liu, {Hsiang Hsuan} and Poon, {Sheung Hung} and Wang, {Yue Li}",
year = "2013",
doi = "10.1007/978-3-642-40164-0_19",
language = "English",
isbn = "9783642401633",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "183--194",
booktitle = "Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings",
note = "19th International Symposium on Fundamentals of Computation Theory, FCT 2013 ; Conference date: 19-08-2013 Through 21-08-2013",
}