4
$\begingroup$

Given a connected and directed graph $G=(V,E)$ with positive weights on the edges. for every $t>0$ we define $E(t)$ to be the group of edges with weight lower or equal than $t$. I need to find an efficient algorithm which computes the minimal $t$ such that $G(t)=(V,E(t))$ is connected.

I can sort all the edges with $|E|\log|E|$ complexity and try to take edges out of the graph from the heaviest to the easiet one, and to check with DFS if it is still connected, but its not effiecnt enough,

Any suggestions?

Improve this question
$\endgroup$
2
  • $\begingroup$ What is "efficient enough" for you? What do you want the algorithm for, or is it an exercise? $\endgroup$
    – Raphael
    Aug 28, 2012 at 12:20
  • $\begingroup$ It's an exercise. Efficient enough is the quickest you can come up with, and of course not the trivial solution. $\endgroup$
    – Jozef
    Aug 28, 2012 at 12:55

1 Answer 1

Reset to default
8
$\begingroup$
  1. Compute a minimum bottleneck spanning tree of the graph. (Actually just compute a minimum spanning tree, as a minimum spanning tree is a minimum bottleneck tree.)
  2. Determine the maximum edge weight from MBST, this will be your $t$.
  3. Remove all edges whose weight is higher.

This can be done in linear time in the sum of the number of nodes and edges (see wiki).

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm sorry, we didn't learn about the minimum bottleneck tree in class. I am afraid I can't use it. $\endgroup$
    – Jozef
    Aug 28, 2012 at 10:52
  • 3
    $\begingroup$ If you read the answer more carefully, you will realise that you can use minimum spanning trees. You just need to prove the the maximum edge in the MST is minimal. $\endgroup$
    – Dave Clarke
    Aug 28, 2012 at 10:53
  • $\begingroup$ You right. I understand the answer. Thanks a lot Dave. $\endgroup$
    – Jozef
    Aug 28, 2012 at 11:01
  • $\begingroup$ How come it's linear? Finding MST is not linear. $\endgroup$
    – Jozef
    Aug 28, 2012 at 15:26
  • $\begingroup$ Oops. Linear in the number of nodes plus edges (if weights are integers). $\endgroup$
    – Dave Clarke
    Aug 28, 2012 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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