A method for identifying maximal independent sets in parallel may include, on a processor, accessing data representing an undirected graph, generating a respective initial priority value for each vertex, dependent on the vertex degree and an average degree for vertices in the graph, and recording an indication of the initial priority value for each vertex. The method may include determining, for multiple vertices, that no neighbor vertex has a priority value that is higher than that of the vertex. In response, the method may include recording respective indications that each neighbor vertex connected is not to be included in a maximal independent set for the undirected graph and recording an indication that the vertex is to be included in the maximal independent set. The determinations and recordings may be performed in parallel by respective processing elements of the processor. The processor may be a GPU.