Name
Title | ||
|---|---|---|
A randomized algorithm for determining dominating sets in graphs of maximum degree five |
Abstract | ||
|---|---|---|
The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.08.011 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
suggested algorithm,algorithm halt,maximum degree,Las Vegas technique,polynomial-time approximation,local dominating set,appropriate message,randomized algorithm,Randomized algorithm,dominating set,Minimum dominating set,Polynomial-time approximation algorithm,2-separated collection | Journal | 410 |
Issue | ISSN | Citations |
47-49 | Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.36 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Soheir M. Khamis | 1 | 21 | 4.87 |
| Sameh S. Daoud | 2 | 8 | 2.66 |
| Hanaa A. E. Essa | 3 | 1 | 0.36 |