Optimal broadcast domination in polynomial time (Q856876)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Optimal broadcast domination in polynomial time |
scientific article; zbMATH DE number 5080069
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Optimal broadcast domination in polynomial time |
scientific article; zbMATH DE number 5080069 |
Statements
Optimal broadcast domination in polynomial time (English)
0 references
14 December 2006
0 references
From the authors' abstract: Broadcast domination was introduced in 2002 as a variant of the standard domination problem such that different vertices can be assigned different domination powers. Since the presentation of the problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, it is shown that it is in P.
0 references
domination in graphs
0 references
broadcast domination
0 references
polynomial time algorithm
0 references
