@article{ART001573805},
author={Sang-Un, Lee and MyeongBok Choi},
title={A Polynomial Time Algorithm for Vertex Coloring Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2011},
volume={16},
number={7},
pages={85-94}
TY - JOUR
AU - Sang-Un, Lee
AU - MyeongBok Choi
TI - A Polynomial Time Algorithm for Vertex Coloring Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2011
VL - 16
IS - 7
PB - The Korean Society Of Computer And Information
SP - 85
EP - 94
SN - 1598-849X
AB - The Vertex Coloring Problem hasn't been solved in polynomial time, so this problem has been known as NP-complete. This paper suggests linear time algorithm for Vertex Coloring Problem (VCP). The proposed algorithm is based on assumption that we can't know a priori the minimum chromatic number for graph . This algorithm divides Vertices of graph into two parts as independent sets and cover set , then assigns the color to . The element of independent sets is a vertex that has minimum degree and the elements of cover set are the vertices that is adjacent to . The reduced graph is divided into independent sets and cover set again until no edge is in a cover set . As a result of experiments, this algorithm finds the perfectly for 26 Graphs that shows the number of selecting is less than the number of vertices .
KW - Minimum Vertex Cover (MVC);Maximum Independent Set (MIS);Minimum Degree ();Vertex Coloring Problem;Chromatic Number ()
DO -
UR -
ER -
Sang-Un, Lee and MyeongBok Choi. (2011). A Polynomial Time Algorithm for Vertex Coloring Problem. Journal of The Korea Society of Computer and Information, 16(7), 85-94.
Sang-Un, Lee and MyeongBok Choi. 2011, "A Polynomial Time Algorithm for Vertex Coloring Problem", Journal of The Korea Society of Computer and Information, vol.16, no.7 pp.85-94.
Sang-Un, Lee, MyeongBok Choi "A Polynomial Time Algorithm for Vertex Coloring Problem" Journal of The Korea Society of Computer and Information 16.7 pp.85-94 (2011) : 85.
Sang-Un, Lee, MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. 2011; 16(7), 85-94.
Sang-Un, Lee and MyeongBok Choi. "A Polynomial Time Algorithm for Vertex Coloring Problem" Journal of The Korea Society of Computer and Information 16, no.7 (2011) : 85-94.
Sang-Un, Lee; MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. Journal of The Korea Society of Computer and Information, 16(7), 85-94.
Sang-Un, Lee; MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. Journal of The Korea Society of Computer and Information. 2011; 16(7) 85-94.
Sang-Un, Lee, MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. 2011; 16(7), 85-94.
Sang-Un, Lee and MyeongBok Choi. "A Polynomial Time Algorithm for Vertex Coloring Problem" Journal of The Korea Society of Computer and Information 16, no.7 (2011) : 85-94.
