Optimizing graph vertex coloring
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?
[edit] :
@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]
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.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
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.
You should never let your fears become the boundaries of your dreams.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement