Problem: I have a graph (in this instance, it's represented by a matrix which is $\in \mathbb{R}^{n \times n}$). In the raw graph, all nodes are connected to every other node (except themselves) in some way.
I am wanting to prune the graph using the edge weights (say keep the $m$ largest connections to each vertex and prune everything else), however I need to ensure the following conditions are satisfied:
-
For each vertex, there must exist a path to any other vertex (directly or indirectly).
-
This must be done in such a way to ensure that the graph remains as sparse as possible, keeping the number of connections to a minimum (i.e. only $m$ connections preferred, but more may be required to ensure indirect connectivity).
Is there a reasonably efficient method for doing this? I realize that the computational cost will be a function $n$, and likely NP hard, but I'd like to keep the cost as low as possible. In some of my applications, $n$ may be a few hundred.
Best Answer
It sounds like you're looking for a minimum spanning tree. There are all sorts of popular algorithms for obtaining a minimum spanning tree; for example, Kruskal's algorithm can do this in $O(|E| \log |V|)$ by using an appropriate data structure.