Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?

  • 1
    $\begingroup$ computer.org/csdl/proceedings/focs/2014/6517/00/6517a384.pdf $\endgroup$ – Neal Young Apr 2 '16 at 23:23
  • $\begingroup$ This paper assumes the nodes on the left side are arriving. It is different problem setting from mine. $\endgroup$ – Chuancong Gao Apr 3 '16 at 2:30
  • $\begingroup$ @Chuancong, I think you should update your questions explaining in it why the solution in the link Neal provided does answer yours. That way people can tailor their comments and answers to the question you really want an answer for. $\endgroup$ – Kaveh Apr 23 '16 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.