CODEWITHSUNDEEP
algorithmgraph
copperhead
copperhead

Reputation: 677

A graph problem

I am struggling to solve the following problem

http://uva.onlinejudge.org/external/1/193.html

However Im not able to get a fast solution.

And as seen by the times of others, there should be a solution of maximum n^2 complexity

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problemid=129&page=problem_stats

Can I get some help?

Upvotes: 2

Views: 607

Answers (3)

IVlad
IVlad

Reputation: 43477

You can only solve this in exponential complexity, but that's not as bad as it sounds, because in practice you'll be able to avoid a lot of bad decisions and thus reduce the running time of the algorithm significantly.

In short, you have to run a DF search from a node and try to color as many nodes black as you can. If you're at a node that has neighboring black nodes, that node can only be white. Keep doing this for every possibility of coloring a specific node.

If you can't figure it out, then check these two code snippets I found by googling for the problem name: one and two. The authors say they get AC, but I haven't tested them. They look correct however.

Upvotes: 1

zengr
zengr

Reputation: 38899

Bron–Kerbosch algorithm

I have solved a similar problem on FaceBook puzzles, I used the B-K algo for that.

Upvotes: 0

Chad Brewbaker
Chad Brewbaker

Reputation: 2579

It is solving the problem called maximum clique, also called maximum independent set or maximum stable set. It is NP-Complete. Fastest code I know for small graphs is Cliquer: http://users.tkk.fi/pat/cliquer.html

If you are writing your own for educational purposes it is probably most efficient to do a depth first search coloring nodes black one at a time and retreating up the DFS if two black nodes are touching.

The easiest to code solution is implementing a binary counter and trying all 2^n possibilities.

Upvotes: 0

Related Questions