Informace o publikaci
Capacitated partial inverse maximum spanning tree under the weighted Hamming distance
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Combinatorial Optimization |
| Citace | |
| Doi | http://dx.doi.org/10.1007/s10878-019-00433-x |
| Klíčová slova | Partial inverse combinatorial optimization problem; Spanning tree; Hamming distance; Computational complexity |
| Popis | Given an edge weighted graph, and an acyclic edge set, the goal of partial inverse maximum spanning tree problem is to modify the weight function as little as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the weighted Hamming distance. Under the weighted sum Hamming distance, if the given edge set has at least two edges, we show that this problem is APX-Hard even without the capacitated constraint; if the given edge set contains only one edge, we present a strongly polynomial time algorithm to solve it. Under the weighted bottleneck Hamming distance, we present an algorithm with time complexity O(mlog2m) where m is the number of edges of the given graph. |