Back to Search Start Over

Complexity Analysis of 2-Heterogeneous Minimum Spanning Forest Problem

Authors :
Zhang, Zhujun
Sun, Qiang
Publication Year :
2016

Abstract

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.<br />Comment: 3 pages, 1 figure

Subjects

Subjects :
Computer Science - Computational Complexity

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1601.04125
Document Type :
Working Paper

Tools

Authors Abstract Subjects Details