Wissen, was gut ist. Studieren in Chemnitz.
Artmann, Sarah; Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo : Random Procedures for Dominating Sets in Graphs

Artmann, Sarah ; Göring, Frank ; Harant, Jochen ; Rautenbach, Dieter ; Schiermeyer, Ingo : Random Procedures for Dominating Sets in Graphs

Author(s):
Artmann, Sarah
Göring, Frank
Harant, Jochen
Rautenbach, Dieter
Schiermeyer, Ingo
Title:
Random Procedures for Dominating Sets in Graphs
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 10, 2008
Mathematics Subject Classification:
05C69 [ Dominating sets, independent sets, cliques ]
60C05 [ Combinatorial probability ]
Abstract:
We present and analyze some random prozedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures.
Keywords:
domination; independence; probabilistic method
Language:
English
Publication time:
5 / 2008