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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Partial Inverse Minimum Spanning Tree Problems

  • Xiucui Guan,
  • Panos M. Pardalos,
  • Binwu Zhang

摘要

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.