Improved distributed -coloring

Area of Science:

• Computer Science
• Distributed Computing
• Graph Theory

Background:

• Graph coloring is a fundamental problem in computer science with applications in resource allocation and scheduling.
• Existing randomized distributed algorithms for graph coloring have limitations in terms of the number of rounds required.
• The state-of-the-art algorithm by Panconesi and Srinivasan (1993) has remained unbeaten for 25 years.

Purpose of the Study:

• To develop improved randomized distributed algorithms for graph coloring.
• To reduce the number of rounds required for computing a valid graph coloring.
• To approach the theoretical lower bounds for distributed graph coloring.

Main Methods:

• Development of a randomized distributed algorithm for computing a (Delta)-coloring in non-complete graphs.
• Design of a randomized algorithm for computing a (Delta+1)-coloring when Delta is small.
• Analysis of the number of rounds required by the proposed algorithms.

Main Results:

• A new randomized distributed algorithm achieves (Delta)-coloring in O(log n) rounds for non-complete graphs.
• A second randomized algorithm computes a (Delta+1)-coloring in O(log n) rounds when Delta is small.
• Both algorithms significantly improve upon the previous O(log n) round state-of-the-art algorithm, reducing the number of rounds required.

Conclusions:

• The presented algorithms offer substantial improvements in the efficiency of distributed graph coloring.
• The new algorithms bring the practical performance closer to theoretical limits, advancing the field of distributed graph algorithms.