Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$:

Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all the edges in the cycle are not of heavier weight than $e$.

Find an algorithm that computes $U$.

I have found an algorithm to do it using a modified version of Kruskal algorithm and the union find data structure in $\mathcal{O}(|V|+|E|\alpha(|V|,|E|)$.

My TA said that it can be computed using a linear time algorithm, can you help? I thought of something about modifying the Prim algorithm and then using $10$ Queues for each weight.

  • 1
    $\begingroup$ 1. You seem to have already figured out that this problem is an obfuscated form of a slight restriction of a very well-known graph theory problem; why not spell this out, to save answerers some time? 2. Hint: First consider a restriction in which every edge has weight 1. What algorithm solves this problem? $\endgroup$ – j_random_hacker May 5 '17 at 17:44
  • 1
    $\begingroup$ Hint: there are only 10 possible values for the weight. You can do all sorts of things, like sorting by weight, in $O(1)$ time per edge (e.g., counting sort). $\endgroup$ – D.W. May 5 '17 at 18:50
  • $\begingroup$ @j_random_hacker If all edges are of weight $1$ we just need to run DFS and find all back edges in linear time. But how can we expand this? $\endgroup$ – Don Fanucci May 5 '17 at 19:38
  • $\begingroup$ @D.W. I used sorting in $\mathcal{O}(1)$ for the modified Kruskal algorithm but still you have to use the union find which makes the algorithm above linear time. $\endgroup$ – Don Fanucci May 5 '17 at 19:40
  • $\begingroup$ @j_random_hacker Thank you I figured it out! $\endgroup$ – Don Fanucci May 5 '17 at 19:50

Your Answer

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

Browse other questions tagged or ask your own question.