Publication: Improving the Performance of Graph Coloring Algorithms through Backtracking
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

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
  

Contact:
autodiff.org
Username:
Password:
(lost password)