Evaluate the complexity of this graph coloring algorithm

  • #1
BRN
82
6
Thread moved from the technical forums to the schoolwork forums
Hello everybody,
I should evaluate the complexity of this graph coloring algorithm.
To do this, I use the adjacency matrix in which the graph nodes are the elements on the diagonal, while the elements outside the diagonal indicate if a node is adjacent to another ##(A_{i,j} = 1)## or not Adjacent ##(A_{i,j} = 0)##.
The algorithm fulfill these steps:
  1. - The number of coloring nodes is counted (NoDesNotCol function);
  2. - For each not colored node, calculating the degree of saturation and note the row index of the node with maximum saturation degree (satDeg function);
  3. - In case the degree of saturation is equal to that of another node, then consider the maximum node degree (nodeDeg function);
  4. - The row index found is passed as a argument to the function that colores the node (setColor function);
  5. - All this is repeated until all the nodes are colored.
Code:
int nColoredNodes = 0.;
unsigned int nodesToColor = nodesNotCol(adjMat);
while( nColoredNodes < nodesToColor)
{
    int max = -1, index = -1;
    for (int i = 0; i < adjMat.size(); ++i)
    {
        if (adjMat[i][i] == 0.)
        {
            int sDegree = satDeg(i, adjMat, matOrder);
            if (sDegree > max) { max = sDegree; index = i ; }
            else if (sDegree == max)
            {
                if (nodeDeg(i, adjMat) > nodeDeg(index, adjMat)) index = i;
            }
        }
    }
    adjMat[index][index] = setColor(index, adjMat, matOrder);
    nColoredNodes++;
}

Calculating the equation of recurrence considering that:
  • - noesnotcol is ##O(n)##;
  • - satDeg is ##O(n^2)##;
  • - nodeDeg is ##O(n)##;
  • - setColor is ##O(n^2)##;
in case ##n=1##:
the cost is 1 for NodesNotCol, 1 for Satdeg, 1 for Nodedeg, 1 for SetColor. Then $$T(1) = 1 + 1 * (1 * (1 + 1) +1) = 4$$

In case ##n>1##:
$$T(n) = n + n (n (n + n^2) + n^2) = n^4 + 2n^3 + n$$

So this algorithm has complexity ##O(n^4)##? Is right what I did?
 

Answers and Replies

  • #2
BRN
82
6
OK, some correction:
setDeg is ##O(\sqrt n n)##
setColor is ##O(\sqrt n n)##

The equation of recurrence should be

##
T(n)=\left\{\begin{matrix}
4 & n=1\\
n+n(n(n+\sqrt n n)+\sqrt n n)& n > 1
\end{matrix}\right.
##

On this I'm pretty sure. Now the question is:
With an equation of recurrence for the worst case

##T(n)=(1+\sqrt n)n^3+\sqrt n n^2 + n##

Is it possible to say that asymptotically is ##O(n^3)##?
 

Related Threads on Evaluate the complexity of this graph coloring algorithm

  • Last Post
Replies
8
Views
8K
Replies
2
Views
524
Replies
8
Views
942
Replies
1
Views
1K
  • Last Post
Replies
0
Views
2K
Replies
1
Views
1K
Replies
12
Views
3K
Replies
1
Views
673
Replies
12
Views
3K
  • Last Post
2
Replies
45
Views
14K
Top