Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Methods to Color Graphs And Find Cliques

IP.com Disclosure Number: IPCOM000100835D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Related People

Philips, TK: AUTHOR

Abstract

Disclosed in this disclosure are 1. A new graph invariant, the Clique Potential, which is defined to be the sum of the degrees of a node and all its neighbors. The Clique Potential is a measure of the likelihood that a node belongs to a large clique. 2. Two graph-coloring algorithms which exploit the Clique Potential. 3. A clique-finding algorithm which exploits the Clique Potential.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 65% of the total text.

Methods to Color Graphs And Find Cliques

       Disclosed in this disclosure are
1.   A new graph invariant, the Clique Potential, which is defined to
be the sum of the degrees of a node and all its neighbors.  The
Clique Potential is a measure of the likelihood that a node belongs
to a large clique.
2.   Two graph-coloring algorithms which exploit the Clique
Potential.
3.   A clique-finding algorithm which exploits the Clique Potential.

      The two graph-coloring algorithms that use the Clique Potential
are next presented.
1.   The highest clique potential first algorithm.
          Order the nodes in descending order of their clique
potential.
          Color the node of highest clique potential with color 1.
          Color subsequent nodes with the smallest color not used on
any adjacent node.
2.   The modified saturation degree algorithm -1-.
          Color the node of highest clique potential with color 1.
          Loop while uncolored nodes remain.
          Select the node which has the largest number of distinct
colors adjacent to it (break ties using the clique potential of the
node).
          Color it with the smallest color not used on any adjacent
node.
          End Loop

      The first algorithm has complexity O(NlogN+E) while the second
one has O(N2).  Tests on random graphs show these algorithms to use
somewhat fewer colors that other algorithms of simila...