WANG Fangyang, LIU Yuming. Extended Kuhn-Munkres algorithm for constrained matching search[J]. Journal of Beijing Normal University(Natural Science), 2021, 57(2): 167-172. DOI: 10.12202/j.0476-0301.2019242
Citation: WANG Fangyang, LIU Yuming. Extended Kuhn-Munkres algorithm for constrained matching search[J]. Journal of Beijing Normal University(Natural Science), 2021, 57(2): 167-172. DOI: 10.12202/j.0476-0301.2019242

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.
  • loading

Catalog

    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return
    Baidu
    map