TAILIEUCHUNG - A new efficient RLF-like algorithm for the vertex coloring problem

The Recursive Largest First (RLF) algorithm is one of the most popular greedy heuristics for the vertex coloring problem. It sequentially builds color classes on the basis of greedy choices. In particular, the first vertex placed in a color class C is one with a maximum number of uncolored neighbors, and the next vertices placed in C are chosen so that they have as many uncolored neighbors which cannot be placed in C. | Yugoslav Journal of Operations Research 26 (2016), Number 4, 441–456 DOI: A NEW EFFICIENT RLF-LIKE ALGORITHM FOR THE VERTEX COLORING PROBLEM Mourchid ADEGBINDIN D´epartement de g´enie informatique et g´enie logiciel Polytechnique Montr´eal Alain HERTZ D´epartement de math´ematiques et de g´enie industriel Polytechnique Montr´eal ¨ Martine BELLAICHE D´epartement de g´enie informatique et g´enie logiciel Polytechnique Montr´eal Received: November 2015 / Accepted: January 2016 Abstract: The Recursive Largest First (RLF) algorithm is one of the most popular greedy heuristics for the vertex coloring problem. It sequentially builds color classes on the basis of greedy choices. In particular, the first vertex placed in a color class C is one with a maximum number of uncolored neighbors, and the next vertices placed in C are chosen so that they have as many uncolored neighbors which cannot be placed in C. These greedy choices can have a significant impact on the performance of the algorithm, which explains why we propose alternative selection rules. Computational experiments on 63 difficult DIMACS instances show that the resulting new RLF-like algorithm, when compared with the standard RLF, allows to obtain a reduction of more than 50% of the gap between the number of colors used and the best known upper bound on the chromatic number. The new greedy algorithm even competes with basic metaheuristics for the vertex coloring problem. Keywords: Graph coloring, Greedy algorithm. 442 M. Adegbindin, A. Hertz, M. Bella¨ıche / A New Efficient RLF-Like Algorithm MSC: 05C15, 05C85. 1. INTRODUCTION Let G be an undirected graph. A vertex coloring of G is the assignment of a color to every vertex such that no two adjacent vertices have the same color. The chromatic number χ(G) of G is the minimum number of colors used in a vertex coloring of G. A stable set is a set of pairwise non

• Toán học
• Graph coloring
• Greedy algorithm
• Recursive Largest First
• Greedy heuristics
• Uncolored neighbors
• Radio coloring
• Channel assignment
• Graph coloring generalization
• Channel transmissions
• Heuristic algorithm
• Evolutionary computation
• Graph coloring problem
• Combinatorial optimization
• Bandwidth multicoloring problem
• Bandwidth coloring problem
• Traffic control
• Signalized intersection
• Signal group
• Grouping traffic streams
• Probabilistic Combinatorial Optimization
• Probabilistic Graph problems
• Probabilistic Minimum Coloring
• The Probabilistic Longest Path
• Probabilistic Minimum Vertex
• the Probabilistic Maximum Independen
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• báo cáo của tạp chí Department of Mathematic
• các giải thuật xếp lịch
• Tìm kiếm địa phương
• Các bài toán kinh điển
• Mô hình hóa
• Bài toán tín chỉ
• simulated anealing
• Algorithm design
• Lecture Algorithm design
• Algorithm analysis
• Poly time reductions
• Constraint satisfaction problems
• Lecture Design and Analysis of Algorithms
• Bài giảng Thiết kế và phân tích thuật toán
• Analysis of Algorithms
• Design of Algorithms