We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Novel Exact Algorithm for Graph Coloring via Implicit Enumeration.
- Authors
Zhang Kai; Yi Jiaren; Zhu Enqiang; Shi Xiaolong; Liu Ziyan
- Abstract
This paper proposes a quick exact algorithm for the graph coloring problem. The algorithm is based on implicit enumerating the coloring sequences of graph and converting the conflict edges constraints into carry numbers, which avoid exponential unnecessary graph coloring sequences testing. Only polynomial memory is needed in our algorithm, and symmetrical coloring solutions obtained by color permutations were removed. The algorithm performs reasonably well on a set of 61 benchmark graphs.
- Subjects
GRAPH coloring; COMBINATORIAL enumeration problems; INFORMATION storage &; retrieval systems; BENCHMARK problems (Computer science); ALGORITHMS; COMPUTER networks
- Publication
International Review on Computers & Software, 2013, Vol 8, Issue 1, p422
- ISSN
1828-6003
- Publication type
Article