1
$\begingroup$

A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given almost tree graph $G$ with distinct edge weight costs that computes a minimum spanning tree of $G$ in time $O(n)$?

$\endgroup$
  • $\begingroup$ You can use LaTeX to typset mathematics, rather than doing it manually with italics. I edited to show you how; we also have a brief tutorial. $\endgroup$ – David Richerby Oct 17 '18 at 17:55
  • 1
    $\begingroup$ I appreciate it -- looks more appropriate that way $\endgroup$ – Shandy Sulen Oct 17 '18 at 20:20
0
$\begingroup$

Here is the description of a desired algorithm in Python style pseudocode.

Generate a spanning tree T of G
Put all remaining edges that are not in T in a list L
For each edge e in L:
  Find the cycle C in the graph that is T plus edge e.
  If e is lighter than the heaviest edge e' in C:
    add e to T and remove e' from T

It requires $O(n)$ operations to generate a spanning tree. It requires $O(n)$ operations to find a cycle when you add an edge to a tree and $O(n)$ operations to find the heaviest edge in a cycle. Since there were total $c+1$ edges remaining, where $c+1$ is a constant, the for loop requires $O(n)$ operations. Adding up other operations of small time, we find that the time-complexity of the algorithm is $O(n)$.

The correctness of the above algorithm has been proved in my answer to turn MST of G to MST of G with one new edge. Note that initially T is its own MST.

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