Randomized algorithms and upper bounds for multiple domination in graphs and networks

Andrei Gagarin, Anush Poghosyan, Vadim Zverovich

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

We consider four different types of multiple domination and provide new improved upper bounds for the k- and k-tuple domination numbers. They generalize two classical bounds for the domination number and are better than a number of known upper bounds for these two multiple domination parameters. Also, we explicitly present and systematize randomized algorithms for finding multiple dominating sets, whose expected orders satisfy new and recent upper bounds. The algorithms for k- and k-tuple dominating sets are of linear time in terms of the number of edges of the input graph, and they can be implemented as local distributed algorithms. Note that the corresponding multiple domination problems are known to be NP-complete.

Original languageEnglish
Pages (from-to)604-611
Number of pages8
JournalDiscrete Applied Mathematics
Volume161
Issue number4-5
Early online date27 Jul 2011
DOIs
Publication statusPublished - 1 Mar 2013

Keywords

  • α-domination
  • α-rate domination
  • k-domination
  • k-tuple domination
  • Randomized algorithm

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Cite this