Evaluate the complexity of this graph coloring algorithm

In summary, the conversation discusses the evaluation of the complexity of a graph coloring algorithm. The algorithm uses the adjacency matrix to determine the nodes to color and follows a set of steps to color them. The equation of recurrence for the worst case is determined to be $$T(n)=(1+\sqrt n)n^3+\sqrt n n^2 + n$$ and it can be concluded that the algorithm has a complexity of ##O(n^3)##.
  • #1
BRN
108
10
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?
 
Physics news on Phys.org
  • #2
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 to Evaluate the complexity of this graph coloring algorithm

1. What is a graph coloring algorithm?

A graph coloring algorithm is a method used to assign colors to the vertices of a graph such that no adjacent vertices have the same color.

2. How is the complexity of a graph coloring algorithm evaluated?

The complexity of a graph coloring algorithm is evaluated by analyzing the time and space requirements for the algorithm to run, as well as the number of colors needed to properly color the graph.

3. What factors contribute to the complexity of a graph coloring algorithm?

The complexity of a graph coloring algorithm is influenced by the size and structure of the graph, the chosen coloring strategy, and the efficiency of the algorithm implementation.

4. How does the complexity of a graph coloring algorithm impact its performance?

The complexity of a graph coloring algorithm can greatly affect its performance, with higher complexity leading to longer run times and potentially requiring more resources to complete.

5. Are there any known efficient graph coloring algorithms?

Yes, there are several efficient graph coloring algorithms such as the Greedy Coloring Algorithm, the Welsh-Powell Algorithm, and the Recursive Largest First Algorithm. However, the most efficient algorithm may vary depending on the specific graph being colored.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
15
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
981
  • Engineering and Comp Sci Homework Help
Replies
1
Views
934
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Back
Top