Improving the performance of graph coloring algorithms through backtracking

Sanjukta Bhowmick, Paul D. Hovland

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationComputational Science - ICCS 2008 - 8th International Conference, Proceedings
Pages873-882
Number of pages10
EditionPART 1
DOIs
StatePublished - 2008
Event8th International Conference on Computational Science, ICCS 2008 - Krakow, Poland
Duration: Jun 23 2008Jun 25 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5101 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Computational Science, ICCS 2008
CountryPoland
CityKrakow
Period6/23/086/25/08

Keywords

  • Backtracking
  • Graph coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improving the performance of graph coloring algorithms through backtracking'. Together they form a unique fingerprint.

  • Cite this

    Bhowmick, S., & Hovland, P. D. (2008). Improving the performance of graph coloring algorithms through backtracking. In Computational Science - ICCS 2008 - 8th International Conference, Proceedings (PART 1 ed., pp. 873-882). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5101 LNCS, No. PART 1). https://doi.org/10.1007/978-3-540-69384-0_92