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)$?
1
$\begingroup$
$\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$
$\endgroup$
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.
answered Oct 17 '18 at 17:58
