- #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:

Calculating the equation of recurrence considering that:

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?

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:

- - The number of coloring nodes is counted (NoDesNotCol function);
- - For each not colored node, calculating the degree of saturation and note the row index of the node with maximum saturation degree (satDeg function);
- - In case the degree of saturation is equal to that of another node, then consider the maximum node degree (nodeDeg function);
- - The row index found is passed as a argument to the function that colores the node (setColor function);
- - 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)##;

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?