System, method, and computer program product for performing graph coloring
US9053041B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 1, 2012 |
| Grant date | Jun 9, 2015 |
| Priority date | — |
| Expiry date | Nov 7, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F40/205
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system, method, and computer program product are provided for categorizing a plurality of vertices of a graph into independent sets. A random number is assigned to each vertex in the graph and the assigned number of each vertex is compared to the assigned numbers each of the neighbors of the vertex, where all vertices in the graph that have an assigned number greater than the assigned numbers of each of their neighbors are added to a first independent set, and all vertices in the graph that have an assigned number less than the assigned numbers of each of their neighbors are added to a second independent set separate from the first independent set.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.