Approximation algorithms for capacitated partial inverse maximum spanning tree problem

DOI10.1007/S10898-019-00852-4zbMATH Open1442.90196OpenAlexW2982750370MaRDI QIDQ2176281FDOQ2176281

Xianyue Li, Ruowang Yang, Du Ding-Zhu, Heping Zhang, Zhao Zhang

Publication date: 4 May 2020

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

Full work available at URL: https://doi.org/10.1007/s10898-019-00852-4

Recommendations

• Capacitated partial inverse maximum spanning tree under the weighted Hamming distance
• Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm
• Partial inverse min-max spanning tree problem
• Partial inverse maximum spanning tree problem under the Chebyshev norm
• The partial inverse minimum spanning tree problem when weight increase is forbidden

zbMATH Keywords

approximation algorithmspanning treepartial inverse problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Graph theory
• New Branch-and-Bound Rules for Linear Bilevel Programming
• Minimizing a Convex Cost Closure Set
• Efficient Algorithms for the Inverse Spanning-Tree Problem
• Inverse max + sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) norm
• Weighted inverse minimum spanning tree problems under Hamming distance
• The base-matroid and inverse combinatorial optimization problems.
• The partial inverse minimum spanning tree problem when weight increase is forbidden
• Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance
• 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
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Computational Difficulties of Bilevel Linear Programming
• Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems
• Constrained inverse min-max spanning tree problems under the weighted Hamming distance
• A Faster Algorithm for the Inverse Spanning Tree Problem
• Solving inverse spanning tree problems through network flow techniques
• Inverse max+sum spanning tree problem under weighted \(l_1\) norm by modifying the sum-cost vector
• Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm
• An algorithm for inverse minimum spanning tree problem
• Inverse min-max spanning tree problem under the weighted sum-type Hamming distance
• Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector
• Capacitated partial inverse maximum spanning tree under the weighted Hamming distance
• Capacitated partial inverse maximum spanning tree under the weighted \(l_{\infty }\)-norm

Cited In (7)

• Combinatorial algorithms for restricted inverse optimal value problems on minimum spanning tree under weighted \(l_1\) norm
• Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance
• Capacitated partial inverse maximum spanning tree under the weighted \(l_{\infty }\)-norm
• 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
• Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance

This page was built for publication: Approximation algorithms for capacitated partial inverse maximum spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176281)