CODEWITHSUNDEEP
algorithmgraph-theory
yetanothercoder
yetanothercoder

Reputation: 1709

minimum weight connected subset T of edges algorithm

Consider the problem of finding a minimum weight connected subset T of edges from a weighted connected graph G. The weight of T is the sum of all the edge weights in T. (a) Why is this problem not just the minimum spanning tree problem? Hint: think negative weight edges. (b) Give an efficient algorithm to compute the minimum weight connected subset T.

(c) from Sciena Manual

(a) spanning tree minimizes summary tree weight, but minimum weight connected subset - every pair path weight, so we can reuse same negative edges to reduce each pair path?

(b) decision on the forehead: run dijkstra's alg n times, tracking previous pairs shortest paths. Seems not the best one, other idea - sort all edges and going from the largest - try to remove each and check connectivity...

Upvotes: 3

Views: 1547

Answers (1)

Foo Bah
Foo Bah

Reputation: 26281

For part A:

Consider K3 (triangle) with each edge having a weight of -1.

What is the MST and what is the Minimum-weight connected subset?

Upvotes: 0

Related Questions