@article{ART001804511},
author={Sang-Un, Lee},
title={A Dominating Set Algorithm},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2013},
volume={18},
number={9},
pages={121-129}
TY - JOUR
AU - Sang-Un, Lee
TI - A Dominating Set Algorithm
JO - Journal of The Korea Society of Computer and Information
PY - 2013
VL - 18
IS - 9
PB - The Korean Society Of Computer And Information
SP - 121
EP - 129
SN - 1598-849X
AB - This paper proposes a linear-time algorithm that has been designed to obtain an accurate solution for Dominating Set (DS) problem, which is known to be NP-complete due to the deficiency of polynomial-time algorithms that successfully derive an accurate solution to it. The proposed algorithm does so by repeatedly assigning vertex ν with maximum degree △(G) among vertices adjacent to the vertex υ with minimum degree δ(G) to Minimum Independent DS (MIDS) as its element and removing all the incident edges until no edges remain in the graph. This algorithm finally transforms MIDS into Minimum DS (MDS) and again into Minimum Connected DS (MCDS)so as to obtain the accurate solution to all DS-related problems. When applied to ten different graphs, it has successfully obtained accurate solutions with linear time complexity O(n). It has therefore proven that Dominating Set problem is rather a P-problem.
KW - Dominating Set;Connected DS;Independent DS;Degree
DO -
UR -
ER -
Sang-Un, Lee. (2013). A Dominating Set Algorithm. Journal of The Korea Society of Computer and Information, 18(9), 121-129.
Sang-Un, Lee. 2013, "A Dominating Set Algorithm", Journal of The Korea Society of Computer and Information, vol.18, no.9 pp.121-129.
Sang-Un, Lee "A Dominating Set Algorithm" Journal of The Korea Society of Computer and Information 18.9 pp.121-129 (2013) : 121.
Sang-Un, Lee. A Dominating Set Algorithm. 2013; 18(9), 121-129.
Sang-Un, Lee. "A Dominating Set Algorithm" Journal of The Korea Society of Computer and Information 18, no.9 (2013) : 121-129.
Sang-Un, Lee. A Dominating Set Algorithm. Journal of The Korea Society of Computer and Information, 18(9), 121-129.
Sang-Un, Lee. A Dominating Set Algorithm. Journal of The Korea Society of Computer and Information. 2013; 18(9) 121-129.
Sang-Un, Lee. A Dominating Set Algorithm. 2013; 18(9), 121-129.
Sang-Un, Lee. "A Dominating Set Algorithm" Journal of The Korea Society of Computer and Information 18, no.9 (2013) : 121-129.
