Page 2 of 7
Posted: Sun Oct 26, 2003 8:02 pm
by epsilon0
this problem is a bit harder than it seems.
you have a test different possibilities (not all though)
it might be a good idea to first color nodes that have a lot of connections.
i found the following:
1) if a node is connected to a black node, it has to be white.
otherwise:
2) if a node is connected to 0 or 1 univisited nodes, you might assume that this node is black
3) if a node is connected to 2 or more univisited nodes, you can't assume anything, you have to test both black and white colors.
good luck
I am confused about the input
Posted: Mon Oct 27, 2003 6:12 am
by A Faltoo Fellow
I am a new solver.
I am being confused whether the graph will be connected or not.
Re: I am confused about the input
Posted: Mon Oct 27, 2003 9:33 am
by Sajid
A Faltoo Fellow wrote:
I am being confused whether the graph will be connected or not.
There is no problem whether the graph is connect or not. If the node is not connected with any other node, it must be colored black. get it ?
epsilon0,
ya, I get u. now, i m considering your case. not done yet. Thanx a lot. 
193 Graph Coloring Algorithm - Dynamic programming?
Posted: Sun Nov 23, 2003 10:06 pm
by technobug
I tried a greedy algorithm (that I took out from my mind...) and got WA.... so I am gonna try the brute force + dynamic programming.... but just to check if there is another solution....
I used something like:
1. Get the vertex with less connections
2. Paint it black
3. Paint every vertex connected white
4. Remove those vertex's from the graph (the black one is only connected to the white ones so its ok. the white ones wont influence the other ones which are still in the graph so its ok)
5. Go back to 1 and get the new vertex (which might have changed as we removed some connections)
It worked with most graphs I tried but did not pass the test so I know its not ok....
Anyone knows the "right" way of doing this? I dont want to get AC with a "dumb" brute force - dynamic programming one....
Thanks in advance,
Guilherme Silveira
Posted: Tue Nov 25, 2003 9:18 pm
by Whinii F.
I can't think of a P time class solution, for graph coloring is a well-known NP problem. (Of course this problem is not the exact instance of it) My solution is backtracking and it runs in 0.037.
So, if you have discovered any DP algorithm other than 2^N, it will be no dumb but really great
Posted: Thu Nov 27, 2003 4:15 pm
by technobug
Ne... i did not get it
I got it right when i did the whole backtracking system (with some nice purges, of course)
I am not a real big academic guy... im just starting reading so i saw its a basic algo..... anyhow, this exercice is not really the actual coloring as it allows WHITE-WHITE..... as u said..;.
Posted: Fri Nov 28, 2003 7:47 pm
by Per
The problem is actually Maximal Independent Set. But of course, that's NP-complete as well.
Posted: Sat Nov 29, 2003 7:25 pm
by Whinii F.
Oh, yes I was stupid again
These days I'm getting more stupid and stupidier, huh
193 Graph coloring algo
Posted: Sun Dec 14, 2003 6:30 pm
by Nick
okay I have no idea about NP-complete problems nor any algo to solve them. Can anyone share something to help me especially on this problem?
Is there any way besides backtracking? thx!!
Re: 193 Graph coloring algo
Posted: Sat Dec 27, 2003 1:08 am
by szymcio2001
Nick wrote:okay I have no idea about NP-complete problems nor any algo to solve them. Can anyone share something to help me especially on this problem?
Is there any way besides backtracking? thx!!
In this problem you should write some "simulation" algorithm. Simply write a program that randomly choose nodes (choose random node and delete all connected with him, choose another, etc. while there are some nodes), do it several times (I did it 200 times) and choose the maximum result. It isn't very good way for NP problems but in this task it works.
the exact algorithm
Posted: Sat Dec 27, 2003 12:07 pm
by abishek
Is this problem exactly the same as finding a maximum stable set of a graph?
Are there any good heuristics as the problem says n <= 100 and the exact solution is exponential on n.
193 WA why? What's wrong in my algorithm??????
Posted: Wed Mar 31, 2004 1:37 am
by NightZ-1
Somebody can help me?
Where it can be the error?
Follows mine in/out
My input:
15
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
10 12
1 2
1 3
1 4
2 3
2 5
3 4
4 6
5 8
6 8
7 8
8 9
9 10
14 21
1 2
1 3
1 4
2 3
2 4
2 5
2 6
3 5
3 10
4 6
4 12
5 7
6 7
7 9
7 8
9 14
8 14
12 13
13 14
14 11
11 10
14 24
1 2
1 3
1 4
2 3
2 4
2 5
2 6
3 5
3 10
4 6
4 12
5 7
5 8
6 7
6 9
7 9
7 8
9 8
9 14
8 14
12 13
13 14
14 11
11 10
1 1
1 1
3 2
1 2
2 3
4 3
1 2
2 3
3 4
5 4
1 2
2 3
3 4
4 5
5 5
1 2
2 3
3 4
4 5
5 1
6 10
1 2
2 3
3 4
4 5
5 1
1 6
2 6
3 6
4 6
5 6
7 11
1 2
2 3
3 4
4 5
5 1
1 6
2 6
3 6
4 6
5 6
1 7
100 2
1 2
2 3
20 19
1 10
2 5
3 4
4 9
5 17
6 4
8 19
9 13
10 11
11 14
12 1
13 6
14 3
15 4
16 5
17 8
18 9
19 15
20 4
11 12
7 5
10 5
1 3
8 5
2 6
4 11
3 5
6 5
11 5
1 4
9 5
1 2
35 40
32 34
33 32
35 32
9 33
32 8
12 16
18 14
13 7
30 33
4 30
2 13
27 26
4 29
6 5
10 6
9 6
32 7
3 1
21 3
12 3
2 1
24 12
12 23
22 12
16 14
19 14
14 15
7 6
6 8
13 14
1 4
27 4
5 4
11 30
31 30
32 30
13 25
25 26
6 11
14 17
My output:
3
1 4 5
5
1 5 6 7 9
7
1 5 6 8 9 10 12
6
1 5 6 10 12 14
1
1
2
1 3
2
1 3
3
1 3 5
2
1 3
2
1 3
3
2 5 7
2
1 3
10
2 4 10 12 13 14 16 17 18 19
7
2 3 4 7 8 9 10
20
2 3 4 7 8 10 11 15 16 17 18 19 22 23 24 25 31 33 34 35
no match
Posted: Wed Mar 31, 2004 7:55 am
by sohel
My AC program gives the following output for your input:
[c]
3
1 4 5
5
1 5 6 7 9
7
1 5 6 8 9 10 12
6
1 5 6 10 12 14
0
1
2
1 3
2
1 3
3
1 3 5
2
1 3
2
1 3
3
2 4 7
99
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
11
1 2 3 6 7 8 9 11 15 16 20
7
1 6 7 8 9 10 11
24
1 5 7 8 9 10 11 15 16 17 18 19 20 21 22 23 24 25 27 28 29 31 34 35
[/c]
Posted: Wed Mar 31, 2004 4:07 pm
by NightZ-1
Thanks sohel.
I found my error.
I am using BFS, but in this case I think i will have to use Backtracking. Is this correct ?
Do you know any other solution, more simple than that?
Posted: Thu Apr 01, 2004 5:34 am
by junbin
NightZ-1 wrote:Thanks sohel.
I found my error.
I am using BFS, but in this case I think i will have to use Backtracking. Is this correct ?
Do you know any other solution, more simple than that?
Backtracking is the easiest to code for this problem..