Extended Kuhn-Munkres algorithm for constrained matching search

With Kuhn-Munkres algorithm no optimal matching is founded on matching subset．An extended Kuhn-Munkres algorithm is proposed here to solve this problem of local matching with lower bound constraints, to search for a bipartite graph matching with edge-weights greater than a given threshold from a given matching subset．At present, there is no polynomial algorithm to solve this problem while the time complexity of general search algorithm is exponential．Extended Kuhn-Munkres algorithm constructs a search tree with an intermediate process of Kuhn-Munkres algorithm as nodes．With search priority and pruning, time complexity of searching for result matching is reduced to a polynomial function about the size of bipartite graph and the size of the difference set between the whole matching set and a given matching subset．