Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm

DOI10.1007/s10898-017-0554-5zbMath1393.90104OpenAlexW2748800470MaRDI QIDQ1704922

Xianyue Li, Zhao Zhang, Ding-Zhu Du

Publication date: 13 March 2018

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-017-0554-5

zbMATH Keywords

computational complexitypolynomial time algorithmspanning treepartial inverse problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (10)

Partial inverse min-max spanning tree problem ⋮ Capacitated partial inverse maximum spanning tree under the weighted \(l_{\infty }\)-norm ⋮ Approximation algorithms for capacitated partial inverse maximum spanning tree problem ⋮ Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance ⋮ Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance ⋮ The lower bounded inverse optimal value problem on minimum spanning tree under unit \(l_{\infty}\) norm ⋮ Capacitated partial inverse maximum spanning tree under the weighted Hamming distance ⋮ Capacitated inverse optimal value problem on minimum spanning tree under bottleneck Hamming distance ⋮ Inverse max+sum spanning tree problem under weighted \(l_{\infty}\) norm by modifying max-weight vector ⋮ Partial inverse maximum spanning tree problem under the Chebyshev norm

Cites Work

• Unnamed Item
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Inverse max + sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) norm
• Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems
• On an instance of the inverse shortest paths problem
• The base-matroid and inverse combinatorial optimization problems.
• Inverse combinatorial optimization: a survey on problems, methods, and results
• The partial inverse minimum spanning tree problem when weight increase is forbidden
• Algorithm for constraint partial inverse matroid problem with weight increase forbidden
• Partial inverse assignment problems under \(l_{1}\) norm
• Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
• The partial inverse minimum cut problem withL₁-norm is strongly NP-hard
• Inverse Optimization
• The Complexity of Multiterminal Cuts
• Max flows in O(nm) time, or better
• An $o(n^3 )$-Time Maximum-Flow Algorithm

This page was built for publication: Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm