A Bio-Inspired Algorithm for Maximum Matching in Bipartite Graphs.

Recently, an ancient slime mold, Physarum polycephalum, has been proved being capable of finding shortest path in physical maze environment, which inspires researchers to extract the core foraging mechanism -- positive feedback -- to simulate or model such intelligent behavior. Among most wellknown mathematical models developed so far, physarum solver, has been adopted and extended to solve a plethora of optimization problems in different fields, including computer science, operations research and transportation etc. In this paper, we first adopt and apply a variant of modified physarum solver, called iterative physarum model, to solve bipartite matching problem. Specifically, the maximum bipartite matching problem is first equivalently transformed to single-source single-sink maximum flow problem. Then the iterative physarum model is used to solve the maximum flow problem adaptively. As iterative physarum solver does not involve solving the systems of linear equations associated with global network flow balance constraints, time complexity of updating node status for one iteration can be reduced from O(n3) to O(m), where n and m are numbers of nodes and edges in the graph, respectively. Extensive numerical studies on both sparse and complete bipartite graphs demonstrate the validity and efficiency of this method [ABSTRACT FROM AUTHOR]