Browse Prior Art Database

Method for Improving Graph-Coloring Algorithms

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

Publishing Venue

IBM

Related People

Philips, TK: AUTHOR

Abstract

Disclosed is a method for improving graph-coloring algorithms. It takes as input any graph-coloring algorithm, and constructs from it a new algorithm that is almost always substantially more effective. The method is as follows: 1. Color the graph using any coloring algorithm (say, C1.) 2. Remove a large independent set. 3. If possible, expand the independent set. 4. Delete all the nodes and edges associated with the large independent set. 5. If the resulting graph is nonempty, go to 1.

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

Method for Improving Graph-Coloring Algorithms

       Disclosed is a method for improving graph-coloring
algorithms. It takes as input any graph-coloring algorithm, and
constructs from it a new algorithm that is almost always
substantially more effective.  The method is as follows:
1.   Color the graph using any coloring algorithm (say, C1.)
2.   Remove a large independent set.
3.   If possible, expand the independent set.
4.   Delete all the nodes and edges associated with the large
independent set.
5.   If the resulting graph is nonempty, go to 1.

      Steps 3 and 4 are the key  steps in our algorithm, and it is
they that distinguish our algorithm from other recursive algorithms.
Each of the stages in the algorithm is next detailed.
1.   Color the graph - Any algorithm can be used. The quality of the
coloring produced by the algorithm is weakly dependent on the quality
of the coloring produced by C1 .  A trade-off can therefore be made
between execution speed and the quality of the coloring produced.
The choice of a simple algorithm for C1 will result in fast execution
but will produce a somewhat poorer coloring; more sophisticated
algorithms will take longer to execute but will produce a better
coloring.  As the quality of the final coloring is only weakly
dependent on the quality of the coloring produced by C1, one has a
great deal of latitude in one's choice of an algorithm.
2.   Remove a Large Independent Set - Remove the independent set for
which the sum of the degrees of all of its members is as large as
possible.  This ensures that the reduced graph remains sparse.
Experiments show the average degree of a node to steadily drop as
independent sets are removed.  In comparison, other approaches (which
typically remove the independent set with the maximum number of
nodes) tend to produce an increase in the average degree of a node as
independent sets are removed.
3.   If possible, expand the Independent Set - Two techniques are
used in this phase.  The first attempts to increase the number of
edges that will be removed, and works as follows:  A list containing
all nodes that are adjacent to exactly one node in the independent
set is formed.  The list is pruned to include only those nodes whose
degree is greater than that of the node (in the independent set) that
they are adjacent to, and then sorted in increasing order of the
difference in degree.  Finally, the pair of maximum difference in
degree is exchanged (...