ERA

Download the full-sized PDF of Iterated Greedy Graph Coloring and the Difficulty LandscapeDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3M32NH6Q

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Iterated Greedy Graph Coloring and the Difficulty Landscape Open Access

Descriptions

Author or creator
Culberson, Joseph
Additional contributors
Subject/Keyword
graph coloring algorithms
independent sets
random graphs
Tabu
Type of item
Computing Science Technical Report
Computing science technical report ID
TR92-07
Language
English
Place
Time
Description
Technical report TR92-07. Many heuristic algorithms have been proposed for graph coloring. The simplest is perhaps the greedy algorithm. Many variations have been proposed for this algorithm at various levels of sophistication, but it is generally assumed that the coloring will occur in a single attempt. We note that if a new permutation of the vertices is chosen which respects the independent sets of a previous coloring, then applying the greedy algorithm will result in a new coloring in which the number of colors used does not increase, yet may decrease. We introduce several heuristics for generating new permutations that are fast when implemented and effective in reducing the coloring number. The resulting Iterated Greedy algorithm(IG) can obtain colorings in the range 100 to 103 on graphs in G(1000,1/2). More interestingly, it can optimally color k-colorable graphs with k up to 60 and n=1000, exceeding results of anything in the literature for these graphs. We couple this algorithm with several other coloring algorithms, including a modified Tabu search, and one that tries to find large independent sets using a pruned backtrack. With these combined algorithms we find 86 and 87 colorings for G(1000,1/2). Finally, we explore the areas of difficulty in probabilistic graph space under a natural parameterization. Specifically, we check our system on k-colorable graphs in G(300,p,k) for 0.05<=p<=0.95 and 2<=k<=105. We find a narrow ridge where the algorithms fail to find the specified coloring, but easy success everywhere else.
Date created
1992
DOI
doi:10.7939/R3M32NH6Q
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:02:31.219+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1062589
Last modified: 2015:10:12 20:46:48-06:00
Filename: TR92-07.pdf
Original checksum: 2d06ffe92c7d9373ee0844949fd1c4ef
Well formed: true
Valid: true
Page count: 58
Activity of users you follow
User Activity Date