Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees with the maximum number of white edges. Do it in linear time ($O(|V|+|E|$).

So basically I want to utilize Prim's algorithm; Suppose the heaviest weight of all white edges is $WMAX$ then we can add this value for every black edge's weight. Now, white edges will be prioritized over black edges.

Now, Prim's algorithm complexity time is defined by it's priority queue implementation. Therefore, I need to use an array of lists (I guess) with a fixed size.

We can maintain a pointer to the minimum value so extraction could be done in $O(1)$ but what about the DECREASE-KEY operation?

To conclude,
How should I implement the priority queue in order to keep it linear?

  • $\begingroup$ I am afraid, you cannot simply add $WMAX$ to all the weight of all black edges. Consider the complete graph with three nodes in which there is one black edge with weight 1 and two white edges with weight 3. Every MST consists of one white and one black edge. However, if you add $WMAX = 3$ to the black edge then Prim's algorithm will pick both white edges. Another approach would be to update $w_{new}(e) = n \cdot w(e)$ for white edges and $w_{new}(e) = n \cdot w(e) + 1$ for black edges. However, this might interfer with the running time of your decrease-key operation (not an expert here). $\endgroup$ – philipph Jul 5 '16 at 8:04
  • $\begingroup$ Okay so maybe $WMAX$ isn't the right option yet we can choose a proper constant for every set of vertices. that's not a problem. $\endgroup$ – LiorGolan Jul 5 '16 at 8:33

Since $0 \leq w(e) \leq 100$ you can use a modified bucket queue as priority queue. For each possible edge weight $w$ you keep a list $A[w]$ of nodes with key $w$. Minimum value extraction can then be accomplished in $\mathcal{O}(100)$ by iterating $w$ from $0$ to $100$ and returning the first element of the first non empty list $A[w]$.

Assume that a node $v$ has key $w$ and a decrease key operation is performed to update the key to $\tilde{w} < w$. Then $v$ must be removed from $A[w]$ (can be done in $\mathcal{O}(1)$ if, for example, linked lists are used and each node stores a pointer to its position in the list) and inserted into $A[\tilde{w}]$ (can again be accomplished in $\mathcal{O}(1)$).

In order to prioritize white edges, you could modify the insertion into the lists such that white edges are always inserted at the front and black edges at the back of a list.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.