Graph Coloring Analysis Project

This project was done for CS7350 - Algorithm Engineering

Project Summary

• Implement Graph generation algorithms for:
  • Complete Graphs
  • Cycle Graphs
  • Random Graphs
• The Random Graphs can have three edge distributions:
  • Uniform
  • Skewed linearly to lower values
  • Custom (Skewed linearly to higher values)
• Implement six vertex ordering algorithms:
  • Smallest Last Vertex
  • Largest Last Vertex
  • Smallest Original Degree Last
  • Largest Original Degree Last
  • Random
  • Depth - First Search
• Implement a graph coloring algorithm that colors based on the ordering from the six algorithms
• Analyze the runtime complexity of all algorithms
• Analyze the efficiency of coloring the graphs