Partial Inverse Minimum Spanning Tree Problems
摘要
This chapter introduces the partial inverse minimum spanning tree problem (PInvMST). Given an edge-weighted graph and an acyclic edge set, the target of (PInvMST) is to get a new weight vector such that the given edge set is included in some minimum spanning tree with respect to the new weight vector, and the difference between the two vectors is minimum. Firstly, we show the computational complexities of (PInvMST) in some special cases and general case under different norms and provide exact algorithms for polynomial time solvable cases. Then, for some cases that have been proven to be \(\mathcal {N}\mathcal {P}\) -hard, we introduce their approximation algorithms and analyze their approximation ratios. Finally, we summarize the conclusion and look forward to future works.