CODEWITHSUNDEEP
algorithmgraphrangeminimumspanning-tree
IronMan007
IronMan007

Reputation: 93

Algorithm for finding spanning tree with minimum range in a given graph

Given a weighted undirected graph G(v,e) with weights w(e), find the set of edges such that each pair of vertices (u,v)∈G are connected (in short, spanning tree) and the range of weights of selected edges is minimum (or the difference between the minimum weight and the maximum weight is minimum).

I tried greedy approach in which sorted the edges with respect to weights and then selected two edges with minimum weight difference between the consecutive edges (g[index = current_left],g[index+1 = current_right]) in the sorted array, subsequently I moved left or right depending on the minimum difference between the (current_left,current_left-j) or (current_right,current_right+j) where j is incremented till we find an edge with at least one non-visited vertex.

For example:

enter image description here

Here the minimum range that we can get is by selecting edges with weight {2,3,5} and the range is 3.

Please point a test case where the suggested algorithm fails and suggest an algorithm for finding such spanning tree.

Edit:

Expected time complexity is O(|E|log|E|) where |E| is number of edges.

Upvotes: 1

Views: 2937

Answers (2)

Sai Kumar
Sai Kumar

Reputation: 1

The algorithm described by G Bach infact works correctly and has a run time of O(m*m) where m is the number of edges(considering the computation of mst takes O(m) time). This was a question asked in codeforces edu section.

Upvotes: 0

G. Bach
G. Bach

Reputation: 3909

You should be able to do it in O(E * (cost of MST computation)):

T = no tree
for all edge weights w_fix sorted in ascending order:
    for all edges e:
        if w(e) >= w_fix:
            set w'(e) = w(e) - w_fix
        else:
            set w'(e) = infinity
    find MST T' according to w'
    if T == no tree or max edge weight(T) > max edge weight(T'):
        set T := T'
print T

The idea is that some edge weight has to be the minimum edge weight among the edges in an optimal spanning tree; so fix a minimum edge weight and find an MST that only contains edges heavier than that. Since all MSTs are also minimum bottleneck spanning trees, this will work.

Here's an improvement that is optimal up to a log-square factor; the basic idea remains the same.

sort edge array E[] by increasing weights

low := high := 0
opt_low := opt_high := 0
opt := infinity
connected := false

while (high < E.length - 1) or (connected):

    if not connected:
        high = high + 1
    else:
        low = low + 1

    update(connected)

    if connected:
        if E[high].weight - E[low].weight < opt:
            opt = E[high].weight - E[low].weight
            opt_low = low
            opt_high = high

print(opt, opt_low, opt_high)

The idea is to keep a sliding window over the edges and use connectivity to maintain the window. To maintain connectivity information, you would use special data structures. There's a number of them that allow for polylogarithmic time costs to maintain connectivity information for both deleting and adding edges, and you can find information on those data structures in these MIT 6.851 lecture notes.

Upvotes: 3

Related Questions