193 - Graph Coloring
Moderator: Board moderators
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
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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
-
- New poster
- Posts: 3
- Joined: Thu Jul 03, 2003 2:30 pm
- Location: Bangladesh
I am confused about the input


-
- Learning poster
- Posts: 94
- Joined: Sat Oct 05, 2002 5:34 pm
- Location: CS - AIUB, Dhaka, Bangladesh.
- Contact:
Re: I am confused about the input
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 ?A Faltoo Fellow wrote: I am being confused whether the graph will be connected or not.
epsilon0,
ya, I get u. now, i m considering your case. not done yet. Thanx a lot.

Sajid Online: www.sajidonline.com
193 Graph Coloring Algorithm - Dynamic programming?
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
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
-
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
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
So, if you have discovered any DP algorithm other than 2^N, it will be no dumb but really great

JongMan @ Yonsei
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..;.
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..;.
193 Graph coloring algo
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!!
Is there any way besides backtracking? thx!!
-
- New poster
- Posts: 38
- Joined: Mon Dec 09, 2002 1:53 pm
- Location: Poznan, Poland
Re: 193 Graph coloring algo
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.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!!
the exact algorithm
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.
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??????
Somebody can help me?
Where it can be the error?
Follows mine in/out
My input:
Where it can be the error?
Follows mine in/out
My input:
My output: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
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
Last edited by NightZ-1 on Tue Apr 06, 2004 5:16 pm, edited 1 time in total.
no match
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]
[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]