Method and apparatus for improving colorability of constrained nodes in an interference graph within a computer system
US5774730A · kind A · utility
31Cited by
2References
16Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Jul 31, 1995 |
| Grant date | Jun 30, 1998 |
| Priority date | — |
| Expiry date | Jul 31, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/441
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for coloring an interference graph yields a higher number of colored nodes by taking into consideration the colors of neighbors of a node's uncolored constrained neighbors. By assigning a color to a node that is also the color of a neighbor of an uncolored constrained neighbor, one color constraint is removed, increasing the probability of coloring the uncolored constrained neighbor. If more than one of the neighbors of the uncolored constrained neighbors are colored, one of the colors may be selected over the others using an appropriate heuristic.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.