Weighted inverse minimum spanning tree problems under Hamming distance

DOI10.1007/s10878-005-5486-1zbMath1066.90104MaRDI QIDQ1774530

Enyu Yao, Yong He, Binwu Zhang

Publication date: 17 May 2005

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

Full work available at URL: https://doi.org/10.1007/s10878-005-5486-1

zbMATH Keywords

inverse problem; minimum spanning tree; strongly polynomial algorithm

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Capacity inverse minimum cost flow problems under the weighted Hamming distance, Inverse max + sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) norm, Inverse max+sum spanning tree problem under weighted \(l_1\) norm by modifying the sum-cost vector, Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems, Inverse min-max spanning tree problem under the weighted sum-type Hamming distance, Inverse minimum cost flow problems under the weighted Hamming distance, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, Efficient algorithms for the inverse sorting problem with bound constraints under the \(l_{\infty }\)-norm and the Hamming distance, An algorithm for solving the shortest path improvement problem on rooted trees under unit Hamming distance, Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector, On inverse linear programming problems under the bottleneck-type weighted Hamming distance, The center location improvement problem under the Hamming distance, Weighted inverse maximum perfect matching problems under the Hamming distance, Inverse minimum flow problem under the weighted sum-type Hamming distance, Approximation algorithms for capacitated partial inverse maximum spanning tree problem, Capacitated partial inverse maximum spanning tree under the weighted Hamming distance, The shortest path improvement problems under Hamming distance, Inverse maximum flow problems under the weighted Hamming distance, Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes, Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance, Some inverse optimization problems under the Hamming distance, Constrained and bicriteria inverse bottleneck optimization problems under weighted Hamming distance, A WEIGHTED INVERSE MINIMUM CUT PROBLEM UNDER THE BOTTLENECK TYPE HAMMING DISTANCE

Cites Work

• Unnamed Item
• Unnamed Item
• Solution structure of some inverse combinatorial optimization problems
• A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Solving Inverse Spanning Tree Problems Through Network Flow Techniques
• An algorithm for inverse minimum spanning tree problem
• A Faster Algorithm for the Inverse Spanning Tree Problem