# Special case of the $MST-$ Problem

I am working on the following exercise:

Consider an undirected complete graph $$G(V,E)$$ and positive real numbers $$a_1,a_2,\ldots,a_n$$. The task is to find a MST with respect to the edge weights $$w_e = a_ia_j$$ for each $$e = \{i,j\}$$. Provide an algorithm that solves this problem that is as efficient as possible.

It is safe to say that just using Kruskal's or Prim's algorithm will not be sufficient here. So we should use the special structure of $$w$$. I came up with the following idea:

1. Sort the edges in increasing order according to their edge weights. This can be done in $$\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$$ time.
2. Traverse the edges, starting from the smallest and add it to $$T$$ if it contains an unvisited vertex. Mark the newely visited vertices. This can be done in $$\mathcal{O}(\lvert E \rvert)$$ time.

But this algorithm is not as efficient as possible for it has $$\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$$ time complexity. The problem here is the procedure in step 1. Could we somehow leave it out?

Assuming all weights are positive, choose a vertex $$v$$ with the minimum weight and construct the tree from all incident edges with this vertex. The tree is hence a star graph with $$v$$ the center of the star.
The second case is where we have at least one negative weight and one positive weight. Let $$u$$ be a vertex with the maximum positive weight. Let $$v$$ be a vertex with negative weight with maximum absolute value among all negative weights. connect $$u$$ to all vertices with negative weights and $$v$$ to all vertices with positive weights. Be aware of not adding the edge between $$u$$ and $$v$$ twice.