Spanning Tree-based Graph Generation for Molecules

Given a graph G = (V, E) and edge weights w e ≥ 0, our goal is to connect all vertices by a subset of edges F while minimizing its cost e∈F w e . Without loss of generality the optimal solution is a tree which is called the Minimum Spanning Tree (MST). This is perhaps the oldest combinatorial optimization problem; it was first solved by Borůvka in 1926 and Jarník in 1930. Both of the proposed algorithms were variants of the greedy algorithm.