For a graph G with red and blue edges and a constant K, we develop a deterministic linear time algorithm that finds a spanning tree G with exactly red edges K (or returns Falseif such a connecting tree does not exist).
What we have done so far:
Let each red edge have a weight of -1, and each blue edge have a weight of 0.
Find the minimum spanning tree (using the standard linear time algorithm). So, we have a spanning tree T with minimum weight, that is, we used as many red edges as we can, because red edges will reduce only the weight.
If T has fewer red edges K, we return False.
If there are exactly K red edges, we are done, T is the answer.
If the red edges are greater than K, we need to replace them with blue ones.
This is our problem, how do we do it in linear time?
Each added blue edge will create a loop, so remove one red edge from the loop, but how can we achieve linearity this way? Is this even a good approach?
source
share