We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Partial inverse maximum spanning tree in which weight can only be decreased under lp-norm.
- Authors
Li, Xianyue; Zhang, Zhao; Du, Ding-Zhu
- Abstract
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.
- Subjects
INVERSE problems; SEISMIC traveltime inversion; ALGORITHMS; POLYNOMIALS; NUMERICAL analysis
- Publication
Journal of Global Optimization, 2018, Vol 70, Issue 3, p677
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-017-0554-5