Affordable Access

Algorithms for the minimum sum coloring problem: a review

Authors
Publication Date
Source
HAL-UPMC
Keywords
  • Approximation Algorithms
  • Evolutionary Algorithms
  • Heuristics And Metaheuristics
  • Local Search
  • Sum Coloring
  • [Info] Computer Science [Cs]
External links

Abstract

<p>The minimum sum coloring problem (MSCP) is a variant of the well-known vertex coloring problem which has a number of AI related applications. Due to its theoretical and practical relevance, MSCP attracts increasing attention. The only existing review on the problem dates back to 2004 and mainly covers the history of MSCP and theoretical developments on specific graphs. In recent years, the field has witnessed significant progresses on approximation algorithms and practical solution algorithms. The purpose of this review is to provide a comprehensive inspection of the most recent and representative MSCP algorithms. To be informative, we identify the general framework followed by practical solution algorithms and the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the reviewed methods, we wish to encourage future development of more powerful methods and motivate new applications.</p>

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments