Extended Kuhn-Munkres algorithm for constrained matching search
-
-
Abstract
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.
-
-