Precompute the optimal decision trees for all graphs with ≤ log(3) n vertices. Partition the original graph into small subgraphs : soft heap. Find the MST of each subgraph :decision tree. Use the small MSTs to construct the MST of the original graph dense case
