Partial inverse maximum spanning tree in which weight can only be decreased under l(p)-norm
Partial inverse maximum spanning tree in which weight can only be decreased under l(p)-norm
复制标题
部分逆最大生成树，其中权重只能在 l(p)-范数下减少
DOI：
10.1007/s10898-017-0554-5
复制
发表时间：
2018
影响因子：
1.8
通讯作者：
Du Ding-Zhu
中科院分区：
文献类型：
--
作者：
Li Xianyue;Zhang Zhao;Du Ding-Zhu
最大或最小生成树问题是一个经典的组合优化问题。本文考虑权函数只能减的部分逆最大生成树问题。给定一个图，一个非循环边集，和一个边权函数，这个问题的目标是尽可能少地减少权重，使得存在关于包含给定边集的函数。如果给定的边集至少有两条边，我们证明这个问题是APX困难的。如果给定的边集只包含一条边，我们提出了一个多项式时间算法。
The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.