How is the performance
How is the performance(execution time) anybody got with this problem? It looks to me parallel programming is not necessary unless worst case scenario test case is applied? Any thoughts?
| |
Re: How is the performance
How is the performance(execution time) anybody got with this problem? It looks to me parallel programming is not necessary unless worst case scenario test case is applied? Any thoughts?
Finding the minimum number of colours is an NP-complete problem, and is has superpolynomial complexity - O(n!) if brute force is used.
Heuristic algorithms exist that can find a colouring for a graph, that run in polynomial time in the region O(n^2) to O(n^3), but the result is not necessarily the minimum number of colours.
In the problem, nodes are labelled with pairs of letters, allowing a maximum of 676 nodes in the graph. This is so large that the brute force approach would take forever.
mat.
| |
Re: How is the performance
Heuristic algorithms exist that can find a colouring for a graph, that run in polynomial time in the region O(n^2) to O(n^3), but the result is not necessarily the minimum number of colours.
The problem statement specifies that the minimum number of colours necessary to colour the graph is included in the output, so a heurisitc approach alone will not be sufficient to solve this problem, but it could form part of an exact solution.
Andrew.
--
Andrew Marshall
http://www.planetmarshall.co.uk | |
Re: How is the performance
The problem statement specifies that the minimum number of colours necessary to colour the graph is included in the output, so a heurisitc approach alone will not be sufficient to solve this problem, but it could form part of an exact solution.
Andrew.
Technically, the statement is: "...the minimum number of colors that is sufficient to color the input graph...",
not that it is necessary to color the graph.
gleb
| |
Re: How is the performance
Technically, the statement is: "...the minimum number of colors that is sufficient to color the input graph...",
not that it is necessary to color the graph.
gleb
Maybe I misunderstand you, but as I read it, we have to come up with a number (the minimum required) as well as a coloring.
| |
Re: How is the performance
Maybe I misunderstand you, but as I read it, we have to come up with a number (the minimum required) as well as a coloring.
It was my first impression too, but it looks that the question is not necessarily to find the true minimum,
instead, the goal is to try to decrease the given (known minimum?) number K.
It make sense for example, for some huge graphs.
But perhaps we need more clarification on that.
| |
Re: How is the performance
I believe that absolute minimum colors needed is what's being asked for, but of course we need clarification to be absolutely sure.
"The last line of the file should be a message declaring the minimum number of colors that is sufficient to color the input graph"
I can see that "minimum number of colors" could be interpreted as "a smaller value of K", implying a smaller value but not necessarily the absolute minimum, but I think that is more like wishful thinking! :-)
| |
Re: How is the performance
I believe that absolute minimum colors needed is what's being asked for, but of course we need clarification to be absolutely sure.
"The last line of the file should be a message declaring the minimum number of colors that is sufficient to color the input graph"
I can see that "minimum number of colors" could be interpreted as "a smaller value of K", implying a smaller value but not necessarily the absolute minimum, but I think that is more like wishful thinking! :-)
Well, the difference between finding the minimum number of colours, ie the chromatic number, and just 'a' number of colours is pretty gargantuan in terms of coding the solution. The exact text is
"...The last line of the file should be a message declaring the minimum number of colors that is sufficient to color the input graph...."
To me, that is a pretty clear statement that it is the chromatic number, ie the minimum number of colours, that is being asked for. For example, if the chromatic number of the input is 5, and a heuristic results in a colouring using 6 colours, then 6 is not the minimim number of colours required to colour the graph, therefore the output would be incorrect.
Andrew.
--
Andrew Marshall
http://www.planetmarshall.co.uk | |
Re: How is the performance
I believe that absolute minimum colors needed is what's being asked for, but of course we need clarification to be absolutely sure.
"The last line of the file should be a message declaring the minimum number of colors that is sufficient to color the input graph"
I can see that "minimum number of colors" could be interpreted as "a smaller value of K", implying a smaller value but not necessarily the absolute minimum, but I think that is more like wishful thinking! :-)
Well, the difference between finding the minimum number of colours, ie the chromatic number, and just 'a' number of colours is pretty gargantuan in terms of coding the solution. The exact text is
"...The last line of the file should be a message declaring the minimum number of colors that is sufficient to color the input graph...."
To me, that is a pretty clear statement that it is the chromatic number, ie the minimum number of colours, that is being asked for. For example, if the chromatic number of the input is 5, and a heuristic results in a colouring using 6 colours, then 6 is not the minimim number of colours required to colour the graph, therefore the output would be incorrect.
Andrew.
Sorry if it was not clear, but that's what I am saying. The absolute minimum, i.e. chromatic number.
| |
Re: How is the performance
Sorry if it was not clear, but that's what I am saying. The absolute minimum, i.e. chromatic number.
I prefer the exact minimum number of colors, which is a NP complete problem. We need to parallel algorithem to imporve the performace of solution.
| |
Re: How is the performance
I prefer the exact minimum number of colors, which is a NP complete problem. We need to parallel algorithem to imporve the performace of solution.
As I understand it, computing the exact chromatic number of a graph is NP-hard. It may not be in NP at all.
| | |
