KJCKorea
Journal Central

@article{ART001963391},
author={Sang-Un, Lee},
title={Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={2},
pages={63-70}

TY - JOUR
AU - Sang-Un, Lee
TI - Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 2
PB - The Korean Society Of Computer And Information
SP - 63
EP - 70
SN - 1598-849X
AB - In the absence of a polynomial time algorithm capable of obtaining the exact solutions to it, the domaticnumber problem (DNP) of dominating set (DS) has been regarded as NP-complete. This paper suggestspolynomial-time complexity algorithm about DNP. In this paper, I select a vertex vi of the maximumdegree (ΔG) as an element of a dominating set Dv,i =1,2, ⋯k , compute Di+1 from a simplified graph of Vi+1= Vi╲Di, and verify that Di is indeed a dominating set through V╲Di = NG(Di) . When applied to 15various graphs, the proposed algorithm has succeeded in bringing about exact solutions withpolynomial-time complexity O(kn) . Therefore, the proposed domatic number algorithm shows that thedomatic number problem is in fact a P-problem.
KW - Dominating set;Connected DS;Independent DS;Degree;Domatic number
DO -
UR -
ER -

Sang-Un, Lee. (2015). Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem. Journal of The Korea Society of Computer and Information, 20(2), 63-70.

Sang-Un, Lee. 2015, "Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem", Journal of The Korea Society of Computer and Information, vol.20, no.2 pp.63-70.

Sang-Un, Lee "Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem" Journal of The Korea Society of Computer and Information 20.2 pp.63-70 (2015) : 63.

Sang-Un, Lee. Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem. 2015; 20(2), 63-70.

Sang-Un, Lee. "Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem" Journal of The Korea Society of Computer and Information 20, no.2 (2015) : 63-70.

Sang-Un, Lee. Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem. Journal of The Korea Society of Computer and Information, 20(2), 63-70.

Sang-Un, Lee. Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem. Journal of The Korea Society of Computer and Information. 2015; 20(2) 63-70.

Sang-Un, Lee. Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem. 2015; 20(2), 63-70.

Sang-Un, Lee. "Maximum Degree Vertex Domatic Set Algorithm for Domatic Number Problem" Journal of The Korea Society of Computer and Information 20, no.2 (2015) : 63-70.