 | The ACM Journal of Experimental Algorithmics |
Volume 7, Article 10, 2002
by
and
http://www.jea.acm.org/2002/HerrmannChromatic/
Abstract:
We propose a new exact algorithm for finding the chromatic number of
a graph G. The algorithm attempts to determine the smallest
possible induced subgraph G' of G which has the
same chromatic number as G. Such a subgraph is said
critical since all proper induced sub-graphs of G' have a
chromatic number strictly smaller than G'.
The proposed method is particularly helpful when a
k-coloring of a non-critical graph is known, and it has to
be proved that no (k-1)-coloring of G exists.
Computational experiments on random graphs and on DIMACS benchmark
problems demonstrate that the new proposed algorithm can solve
larger problems than previous known exact methods.
Keywords: Algorithms, Experimentation, Performance
Categories: G.4 Mathematical Software: Algorithm Design and Analysis
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- Errata: Five lines are missing in the published versions of Table 2
of this paper. Here is a Postscript version and
PDF version containing the full Table;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated August 11, 2002, by editor@jea.acm.org