#### Archived

This topic is now archived and is closed to further replies.

# Optimizing graph vertex coloring

This topic is 5621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi! I have a bit of a problem with coloring graph vertices. All "standard" algoritem I found (and I understand) use uncolored graph for start, but I need something that starts on partly colored graph (some vertices have fixed color) and need to color the rest of graph. I know how to do this to find minimal coloring but that's O(n!) -> not realy useful. Greedy algo. also works but coloring is not so good(usualy produces 2x-3x more colors than minimal count). I was hoping for something that works in about O(n^3) and gives about ~1.5x colors... Any ideas?  : @moderator : if this is not the right forum to ask please move it somewhere... You should never let your fears become the boundaries of your dreams. [edited by - _DarkWIng_ on May 3, 2003 1:16:50 PM]

##### Share on other sites
This could be the right forum, since the answer may be a math-optimized algorithm. But I don''t really understand the problem. What do you mean by a colored graph exactly? There are different ways to interpret.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

##### Share on other sites
Something simmilar to minimal colored graph(exact solution is NP) using heuristic algo that starts on partly colored graph. I don''t realy know how to explain this very well.

You should never let your fears become the boundaries of your dreams.

##### Share on other sites
Have you tried doing greedy, but always choosing most constrained or least constrained? Also, you may want to try hill-climbing with random restart or simulated annealing.

1. 1
2. 2
3. 3
Rutin
16
4. 4
JoeJ
13
5. 5

• 9
• 9
• 14
• 10
• 25
• ### Forum Statistics

• Total Topics
632646
• Total Posts
3007636
• ### Who's Online (See full list)

There are no registered users currently online

×