System, method, and computer program product for performing graph coloring

摘要

A system, method, and computer program product are provided for categorizing a plurality of vertices of a graph. A predetermined plurality of random numbers is assigned to each vertex of the plurality of vertices, a determination is made whether each of the assigned predetermined plurality of random numbers of a single vertex is greater than a corresponding random number of the assigned predetermined plurality of random numbers of each of the neighbors of the single vertex, and in response to the determination, one of the assigned random numbers is selected from a group of assigned random numbers of the single vertex.

主权项

1. A computer-implemented method, comprising:
identifying a graph with a plurality of vertices; categorizing the plurality of vertices by:
assigning a predetermined plurality of random numbers to each vertex of the plurality of vertices;determining whether each of the assigned predetermined plurality of random numbers of a single vertex is greater than a corresponding random number of the assigned predetermined plurality of random numbers of each of the neighbors of the single vertex;determining whether the Nth assigned number of the single vertex is a local minimum when compared against the Nth assigned number of each of the neighbors of the single vertex; andselecting, in response to the determination, one of the assigned random numbers from a group of assigned random numbers of the single vertex, wherein the categorizing of the plurality of vertices is optimized.