0
$\begingroup$

In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:

H ← ∅
for each (u,v) in the stream 
    H ← (u, v)
    if H includes a cycle 
            remove largest weight edge in the cycle

To make this fast we need a data structure that allows you to check if (u,v) makes a cycle and also allows you to remove the largest weight edge from a cycle.

What is a suitable data structure for this?

$\endgroup$
2
$\begingroup$

By noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens, you can use a ST-Tree[1], which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $a$ to $b$"

Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find). If they are not, you add it as possible. Otherwise, if its weight is smaller than $max( a \to b)$, you replace with $(a,b)$ the max. weight edge.

[1]https://en.wikipedia.org/wiki/Link/cut_tree

$\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.