Jump to content
  • Advertisement

Archived

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

_DarkWIng_

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.

If you intended to correct an error in the post then please contact us.

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? [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]

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!