A Graph Coloring Algorithm for Large Scheduling Problems

Area of Science:

• Computer Science
• Discrete Mathematics
• Algorithm Analysis

Background:

• Graph coloring is a fundamental problem in computer science with applications in resource allocation.
• Existing algorithms face scalability challenges with large and complex graphs.

Purpose of the Study:

• Introduce a new graph coloring algorithm.
• Evaluate its performance against established methods.
• Provide a tool for heuristic evaluation of graph coloring algorithms.

Main Methods:

• Developed a novel graph coloring algorithm.
• Implemented and compared its performance with existing algorithms.
• Created a procedure for generating random test graphs with a known chromatic number.

Main Results:

• The new algorithm exhibits O(n^2) time complexity on sparse graphs.
• It is particularly effective for large-scale scheduling problems.
• Heuristic evaluations using generated test graphs provide insights into algorithm capabilities.

Conclusions:

• The proposed graph coloring algorithm offers an efficient solution for sparse graph problems.
• Its performance characteristics make it suitable for practical applications like scheduling.
• The graph generation procedure is a valuable tool for future algorithm research.