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 and it can be concluded that the algorithm has a complexity of .
  • #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 or not Adjacent .
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 ;
  • - satDeg is ;
  • - nodeDeg is ;
  • - setColor is ;
in case :
the cost is 1 for NodesNotCol, 1 for Satdeg, 1 for Nodedeg, 1 for SetColor. Then

In case :


So this algorithm has complexity ? Is right what I did?
 
Physics news on Phys.org
  • #2
OK, some correction:
setDeg is
setColor is

The equation of recurrence should be



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



Is it possible to say that asymptotically is ?
 

Similar threads

Replies
10
Views
2K
Replies
15
Views
2K
Replies
4
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
2
Views
408
Replies
3
Views
1K
Back
Top