Analysis of a greedy heuristic for finding small dominating sets in graphs (Q1183397)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Analysis of a greedy heuristic for finding small dominating sets in graphs |
scientific article |
Statements
Analysis of a greedy heuristic for finding small dominating sets in graphs (English)
0 references
28 June 1992
0 references
Consider the problem of finding a minimum dominating set in an undirected graph. The author obtains an upper bound on the size of the dominating set returned by the greedy algorithm.
0 references
dominating sets
0 references
greedy heuristic
0 references
