Capacitated partial inverse maximum spanning tree under the weighted Hamming distance

DOI10.1007/s10878-019-00433-xzbMath1433.90178OpenAlexW2954824859MaRDI QIDQ2279743

Xianyue Li, Huijing Huang, Jingjing Bai, Xichao Shu

Publication date: 13 December 2019

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

Full work available at URL: https://doi.org/10.1007/s10878-019-00433-x

zbMATH Keywords

computational complexityspanning treeHamming distancepartial inverse combinatorial optimization problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (8)

Expanding maximum capacity path under weighted sum-type distances ⋮ 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 ⋮ 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
• The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance
• The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance
• Inverse 1-median problem on trees under weighted Hamming distance
• Inverse max + sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) norm
• Heuristic algorithms for the inverse mixed integer linear programming problem
• 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
• Constrained inverse min-max spanning tree problems under the weighted Hamming distance
• Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm
• Weighted inverse minimum spanning tree problems under Hamming distance
• The center location improvement problem under the Hamming distance
• The base-matroid and inverse combinatorial optimization problems.
• Weighted inverse maximum perfect matching problems under the Hamming distance
• The shortest path improvement problems under Hamming distance
• Inverse maximum flow problems under the weighted Hamming distance
• 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
• Solving Inverse Spanning Tree Problems Through Network Flow Techniques
• Weighted Inverse Minimum Cut Problem under the Sum-Type Hamming Distance
• The partial inverse minimum cut problem withL₁-norm is strongly NP-hard
• A WEIGHTED INVERSE MINIMUM CUT PROBLEM UNDER THE BOTTLENECK TYPE HAMMING DISTANCE
• Efficient Algorithms for the Inverse Spanning-Tree Problem
• The Complexity of Multiterminal Cuts
• An algorithm for inverse minimum spanning tree problem
• Minimizing a Convex Cost Closure Set
• A Faster Algorithm for the Inverse Spanning Tree Problem
• Max flows in O(nm) time, or better
• An $o(n^3 )$-Time Maximum-Flow Algorithm

This page was built for publication: Capacitated partial inverse maximum spanning tree under the weighted Hamming distance