2
$\begingroup$

Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \{1,2,...,10\}$.
Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that contains $e$ such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$.

I thought maybe because the weights are bounded I can run Kruskal multiple times and each time delete edges with a specific weight, and that without changing the complexity. Would appreciate your help:)

$\endgroup$
1
$\begingroup$

Suppose $E_{i}$ be the set of all edges that have weight $i$. Now, we want to check if any of these edges are part of the solution or not. Note that, we can simply delete all the edges from the graph of the weight strictly greater than $i$ since they should not come in a cycle containing $e \in E_{i}$. Let $G_{i}$ be the new graph after deletion of these edges. Now, we just have to solve the following new problem:

Updated Problem: Find all the edges in $E_{i}$ that form a cycle in $G_{i}$

Try solving this new problem on your own. In case, you need any help, check this link for the solution to this problem in $O(|V|+|E|)$ time.

Since there are only $10$ such graphs $G_{i}$. The overall time would remain $O(|E|+|V|)$.

$\endgroup$

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.