DOI QR코드

DOI QR Code

A Polynomial Time Algorithm for Vertex Coloring Problem

정점 색칠 문제의 다항시간 알고리즘

  • Lee, Sang-Un (Dept. of Multimedia Science, Gangneung-Wonju National University) ;
  • Choi, Myeong-Bok (Dept. of Multimedia Science, Gangneung-Wonju National University)
  • 이상운 (강릉원주대학교 멀티미디어공학과) ;
  • 최명복 (강릉원주대학교 멀티미디어공학과)
  • Received : 2011.03.11
  • Accepted : 2011.04.29
  • Published : 2011.07.31

Abstract

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 ${\chi}(G)$=k for graph G=(V,E) This algorithm divides Vertices V of graph into two parts as independent sets $\overline{C}$ and cover set C, then assigns the color to $\overline{C}$. The element of independent sets $\overline{C}$ is a vertex ${\upsilon}$ that has minimum degree ${\delta}(G)$ and the elements of cover set C are the vertices ${\upsilon}$ that is adjacent to ${\upsilon}$. The reduced graph is divided into independent sets $\overline{C}$ and cover set C again until no edge is in a cover set C. As a result of experiments, this algorithm finds the ${\chi}(G)$=k perfectly for 26 Graphs that shows the number of selecting ${\upsilon}$ is less than the number of vertices n.

본 논문은 지금까지 NP-완전인 난제로 알려진 정점 색칠 문제를 선형시간 복잡도로 해결한 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 G=(V,E)의 최소 채색수 ${\chi}(G)$=k를 결정하기 위해 사전에 k값을 알지 못한다는 가정에 기반하고 있다. 단지 주어진 그래프를 독립집합 $\overline{C}$와 정점 피복 집합 C로 정확히 양분하여 $\overline{C}$에 색을 배정하는 방법을 적용하였다. 독립집합 $\overline{C}$의 원소는 ${\delta}(G)$인 정점 ${\upsilon}$가, C의 원소는 정점 ${\upsilon}$의 인접 정점들 u가배정된다. 축소된 그래프 C는 다시 $\overline{C}$와 C로 양분되며, 이 과정을 C의 간선이 없을 때까지 수행한다. 26개의 다양한 그래프를 대상으로 제안된 알고리즘을 적용한 결과 정점 ${\upsilon}$를 선택하는 횟수는 정점의 수 n보다 작은 값을 나타내었으며, ${\chi}(G)$=k를 찾는데 성공하였다.

Keywords

References

  1. Wikipedia, "Graph Coloring," http://en.wikipedia.org/wiki/Graph_Coloring, Wikimedia Foundation Inc., 2008.
  2. Wikipedia, "NP-Complete," http://en.wikipedia.org/wiki/NP-Complete, Wikimedia Foundation Inc., 2008.
  3. Wikipedia, "Four Color Theorem," http://en.wikipedia.org/wiki/Four_Color_Theorem, Wikimedia Foun dation Inc., 2008.
  4. J. M. Byskov, "Chromatic Number in Time $O(2.4023^n)$ Using Maximal Independent Sets," BRICS RS-02-45, 2002.
  5. Wikipedia, "Independent Set Problem," http://en.wikipedia.org/wiki/Independent_Set _Problem, Wiki media Foundation Inc., 2008.
  6. Wikipedia, "Degree (Graph Theory)," http://en.wikipedia.org/wiki/Degree_(graph-theory), Wikimedia Foundation Inc., 2008.
  7. R. V. Stee, "Approximations-und Online-Algor ithmen: Vertex Cover und Scheduling Unrelated Machines,"http://algo2.iti.uni-karlsruhe.de/vanstee/courses/, 2007.
  8. M. A. A. Zito, "COMP309: Efficient Sequential Algorithms-Vertex Cover," University of Liverpool, http://www.csc.liv.ac.uk/-michele/TEACHING/COMP309/2005/Lec10.4.4.pdf, 2005.
  9. Y. W. Chang, "Algorithms: Greedy Algorithms," http://cc.ee.ntu.edu.tw/-ywchang/Courses/Alg/unitf.pdf, 2007.
  10. A. Dharwadker, "The Vertex Coloring Algorithm," http://www.geocities.com/dharwadker/vertex_coloring/, 2006.
  11. E. W. Weisstein, "Maximal Independent Vertex Set," http://mathworld.wolfram.com/MaximalIndependentVertexSet.html,Wolfram Research Inc., Mathworld, 2008.
  12. F. Herrmann and A. Hertz, "Finding The Chromatic Number By Means Of Critical Graphs," ACM Journal of Experimental Algorithms, pp. 1-9, 2002.
  13. R. Naserasr and C. Tardif, "The Chromatic Covering Number of a Graph," http://www.math.uwaterloo.ca/-naserasr/pdfs/ccn4.pdf, 2005.
  14. Wikipedia, "Hadwiger Conjecture (Graph Theory)," http://en.wikipedia.org/wiki/Hadwiger_Conjecture(graph_theory), Wikimedia Foundation Inc., 2008.
  15. R. Thomas, "An Update on the Four-Color Theorem," Notices of the American Mathematical Society, Vol. 45, No. 7, 1998.
  16. Wikipedia , "Hadwiger-Nelson Problem," http://en.wikipeia.org/wiki/Hadwiger_Nelson_Problem,Wikimedia Foundation Inc. 2008.

Cited by

  1. 간선 색칠 문제의 다항시간 알고리즘 vol.18, pp.11, 2013, https://doi.org/10.9708/jksci.2013.18.11.159
  2. 평면의 채색수 알고리즘 vol.19, pp.5, 2011, https://doi.org/10.9708/jksci.2014.19.5.019