🔒 Locked

Optimizing graph vertex coloring

Started by _DarkWIng_ May 3, 2003 at 12:14 PM 1 replies 450+ views

Original Post

May 3, 2003 at 12:14 PM

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]

grhodes_at_work

Mod

198

grhodes_at_work

May 5, 2003 at 9:36 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.

_DarkWIng_

Author

_DarkWIng_

May 6, 2003 at 2:37 AM

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.

sjelkjd

120

sjelkjd

May 6, 2003 at 3:41 AM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.