www.Autodiff.org - Publication: Improving the Performance of Graph Coloring Algorithms through Backtracking

Improving the Performance of Graph Coloring Algorithms through Backtracking

- Part of a collection -

Author(s)
Sanjukta Bhowmick , Paul Hovland

Published in
Computational Science -- ICCS 2008

Editor(s)
Marian Bubak, van Albada, Geert Dick, Jack Dongarra, Peter M. A. Sloot

Year
2008

Abstract
Graph coloring is used to identify independent objects in a set and has applications in a wide variety of scientific and engineering problems. Optimal coloring of graphs is an NP-complete problem. Therefore there exist many heuristics that attempt to obtain a near-optimal number of colors. In this paper we introduce a backtracking correction algorithm which dynamically rearranges the colors assigned by a top level heuristic to a more favorable permutation thereby improving the performance of the coloring algorithm. Our results obtained by applying the backtracking heuristic on graphs from molecular dynamics and DNA-electrophoresis show that the backtracking algorithm succeeds in lowering the number of colors by as much as 23%. Variations of backtracking algorithm can be as much as 66% faster than standard correction algorithms, like Culberson’s Iterated Greedy method, while producing a comparable number of colors.

AD Theory and Techniques
graph coloring

BibTeX
@INPROCEEDINGS{
         Bhowmick2008ItP,
       author = "Sanjukta Bhowmick and Paul Hovland",
       title = "Improving the Performance of Graph Coloring Algorithms through Backtracking",
       booktitle = "Computational Science -- ICCS 2008",
       series = "Lecture Notes in Computer Science",
       editor = "Marian Bubak and van Albada, Geert Dick and Jack Dongarra and Peter M. A. Sloot",
       month = "June",
       pages = "873--882",
       doi = "10.1007/978-3-540-69384-0_92",
       ad_theotech = "graph coloring",
       abstract = "Graph coloring is used to identify independent objects in a set and has
         applications in a wide variety of scientific and engineering problems. Optimal coloring of graphs is
         an NP-complete problem. Therefore there exist many heuristics that attempt to obtain a near-optimal
         number of colors. In this paper we introduce a backtracking correction algorithm which dynamically
         rearranges the colors assigned by a top level heuristic to a more favorable permutation thereby
         improving the performance of the coloring algorithm. Our results obtained by applying the
         backtracking heuristic on graphs from molecular dynamics and DNA-electrophoresis show that the
         backtracking algorithm succeeds in lowering the number of colors by as much as 23%. Variations of
         backtracking algorithm can be as much as 66% faster than standard correction algorithms, like
         Culberson’s Iterated Greedy method, while producing a comparable number of colors.",
       year = "2008"
}

back

autodiff.org
Username:
Password: