Please help with the following problem. For part a, it seems like a greedy solut
ID: 3845830 • Letter: P
Question
Please help with the following problem. For part a, it seems like a greedy solution would work? Please give pseudocode.
Given a graph G = (V,E) a k-coloring of the graph is a labeling of the vertices with the colors c1, c2,..,ck such that for every edge (u,v) the color of the u is different from the color of v.
a. Give a linear time algorithm that finds a 2-coloring for a tree.
b. Think about coloring a tree with 2 colors so that you have the max number of nodes colored c1. Prove that the algorithm in part (a)-with a minor modification probably-can be used to solve this problem.
Explanation / Answer
Yes, correct. A greedy algorithm works for part (a). Here is the pseudo code:
Explanation: A vertex is called "VISITED" (in above pseudocode) only it and its children have been colored completely. This process is similar to DFS process by using the stack. Effectively we are traversing each edge only once.
So, time complexity is linear O(|E|) where E = number of vetices in graph.
--------------
(b) Notice that in every connected component of the graph, if we are starting fresh, then first vertex maybe colored in 2 ways - C1 or C2. However all the rest of the vertices have only one choice of coloring. So, there are only 2 ways of coloring a connected component of a graph using two colors.
Therefore, in order to get maximum number of vertices in color C1, we can use the following procedure:
Time complexity: In the worst case, we may need to swap the color of every vertex. This means we have visit every vertex twice - once to count and once to recolor.
So, this is a linear step. Thus, this algorithm effectively keeps the same time complexity as part 1 which is linear.