TY - JOUR
ID - 13804
TI - On the inverse maximum perfect matching problem under the bottleneck-type Hamming distance
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Tayyebi, Javad
AD - Birjand university of technology
Y1 - 2019
PY - 2019
VL - 4
IS - 1
SP - 35
EP - 46
KW - Inverse problem
KW - Hamming distance
KW - perfect matching
KW - binary search
DO - 10.22049/cco.2018.26231.1087
N2 - Given an undirected network $G(V,A,c)$ and a perfect matching $M$ of $G$, the inverse maximum perfect matching problem consists of modifying minimally the elements of c so that M becomes a maximum perfect matching with respect to the modified vector. In this article, we consider the inverse problem when the modifications are measured by the weighted bottleneck-type Hamming distance. We propose an algorithm based on the binary search technique for solving the problem. Our proposed algorithm has a better time complexity than the one presented in [13]. We also study the inverse assignment problem as a special case of the inverse maximum perfect matching problem in which the network is bipartite and present an efficient algorithm for solving the problem. Finally, we compare the algorithm with those presented in the literature.
UR - http://comb-opt.azaruniv.ac.ir/article_13804.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13804_dbb06f4741821880df74fe3c9cca70f8.pdf
ER -