On independence domination

Wing Kai Hon, Ton Kloks, Hsiang Hsuan Liu, Sheung Hung Poon, Yue Li Wang

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationFundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings
Pages183-194
Number of pages12
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event19th International Symposium on Fundamentals of Computation Theory, FCT 2013 - Liverpool, United Kingdom
Duration: 19 Aug 201321 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8070 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Symposium on Fundamentals of Computation Theory, FCT 2013
Country/TerritoryUnited Kingdom
CityLiverpool
Period19/08/1321/08/13

Keywords

  • Cograph
  • Distance-hereditary graph
  • Domination
  • Exact algorithm
  • Independence domination
  • Permutation graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On independence domination'. Together they form a unique fingerprint.

Cite this