1
$\begingroup$

I am given an undirected connected graph with $n$ nodes, average degree $\sqrt{\log n}$, and each edge having integer weight in $\{1,..,5\}$. I am asked to describe MST algorithm which is as efficient as possible.

I read https://en.wikipedia.org/wiki/Minimum_spanning_tree about Dense Graph and Integer weights, but it seems that I cannot satisfy the conditions to apply the strategy for Dense graphs, and it is unclear to me what is the benefit of the integer weights.

I am thinking of simply applying Kruskal or Prim, but then I am not making use of the additional information that I have on the degree and the weights.

Any suggestion is appreciated.

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $G_0$ be your input graph, label each edge $(u,v)$ with $(u,v)$ itself. Repeat the following for all values of $i$ from $1$ to $5$:

  • Compute a spanning forest $F_i$ of the subgraph of $G_{i-1}$ induced by the edges with weight $i$.
  • Construct the graph $G_{i}$ obtained from $G_{i-1}$ by contracting all vertices in the same connected component (i.e., tree) in $F_i$ into a single vertex. For each surviving edge, make sure to preserve the original label (even if one or both the original endvertices are now contracted into a new vertex).

At the end of this process, you can obtain a minimum spanning forest $F$ of $G_0$ by selecting all edges $(u,v)$ such that $(u,v)$ is a label of an edge in some $F_i$. If $G_0$ is connected then $F$ is also a MST of $G_0$.

Since each iteration can be performed in time $O(n \sqrt{\log n})$, the overall time complexity is also $O(n \sqrt{\log n})$. This is clearly optimal since $\Omega(n \sqrt{\log n})$ time is needed just to read the graph.

$\endgroup$
6
  • $\begingroup$ Hmm, wow, this is a lot more involved than I tought. Thanks a lot! $\endgroup$
    – NiRvanA
    Commented Mar 9, 2022 at 21:11
  • $\begingroup$ @JohnL., To compute a spanning forest it is sufficient to perform any visit from an arbitrary vertex of each connected component (all edge weights are the same), so only $O(|E|)$ time is needed. $\endgroup$
    – Steven
    Commented Mar 9, 2022 at 22:15
  • 1
    $\begingroup$ @Steven Indeed, your algorithm does not need hashtable at all assuming appropriate input format. $\endgroup$
    – John L.
    Commented Mar 9, 2022 at 22:23
  • 1
    $\begingroup$ @IIK Or, you can sort all edges by counting sort, which takes $O(|E|)$-time. Then apply Kruskal's algorithm. The time-complexity is $O(n\sqrt{\log n}\alpha(n))$ $\endgroup$
    – John L.
    Commented Mar 9, 2022 at 22:24
  • 1
    $\begingroup$ An easier algorithm is probably Prim's where the priority queue is implemented using $5$ buckets (one for each weight). When we need to extract the minimum, we search for the first non-empty bucket. $\endgroup$
    – Steven
    Commented Mar 9, 2022 at 22:41

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.