TWO-PHASE HYBRID VERTEX CLASSIFICATION

摘要

A processor performs vertex coloring for a graph based at least in part on the degree of each vertex of the graph and based at least in part with another coloring approach, such as comparison of random values assigned to the vertices. For each vertex in the graph, a processor determines whether the degree of the vertex is a local maximum; that is, whether the degree of the vertex is greater than the degree of each of its connected vertices. Each vertex having a local-maximum degree is assigned a specified or randomly selected color, and is then omitted from future iterations of the coloring process. After a stop criterion is met, the processor assigns random values to the remaining uncolored vertices and assigns colors based on comparisons of the random values.

主权项

1. A method comprising:
receiving at a first processor a graph comprising a plurality of vertices, each of the plurality of vertices representing resources of the processor; assigning classifications to each of the plurality of vertices, wherein assigning classifications comprises assigning a first classification to a first vertex of the plurality of vertices according to a first classification technique and assigning a second classification to a second vertex of the plurality of vertices based on a second classification technique different from the first classification technique, so that the first vertex and the second vertex do not share their assigned classifications with any of their connected vertices; and assigning processor resources based on the classifications assigned to the plurality of vertices.