Complexity Analysis of 2-Heterogeneous Minimum Spanning Forest Problem
Zhujun Zhang, Qiang Sun · arXiv (Cornell University) · 2016
For complexity of the heterogeneous minimum spanning forest problem has not been determined, we reduce 3-SAT which is NP-complete to 2-heterogeneous minimum spanning forest problem to prove this problem is NP-hard and spread result to general problem, which determines complexity of this problem. It provides a theoretical basis for the future designing of approximation algorithms for the problem.