For each of these problems give a deterministic algorithm an

For each of these problems, give a deterministic algorithm and a nondeterministic algorithm, and for each algorithm, give its time and space complexity. (Thus, for each problem, you give two algorithms, and for each algorithm, two complexity analyses.) Attempt to be reasonably efficient.

Given a graph G=(V,E) and a set of k colors, can you color the edges of the graph so that no vertex has two or more edges attached to it that have the same color?

Solution

Here given that G=(V,E) where V defines the vertices and E defines edges involved in the given graph and set of k colors are to be used to color the Edge of the graph.

Algorithm Basic Greedy Coloring :

a) Consider the currently picked edge and color it with the lower numbered color that has not been used on any previously colored edges adjacent with common vertex. If all previously used colors appears then a new color will be selected

The above given algorithm has Time complexity represented using O notation as O(E^2 +V)

Naive algorithm can also be used for the above problem by considering all possible configurations that satisfies the given constraints.

while there are untried configurations

{

generate the next configuration

if no adjacent edges are colored with same color

{

print this configuration;

}

}

Here this algorithm is implemented based on the backtracking with complexity of E^k colors. Here the idea is to assign colors one by one to different edges before assigning the color to the edge it consider the safety by considering already assigned colors to the adjacent edges if we find then place the color if not a new color is involved...