That is true for maximum matching (weighted or not) in bipartite graphs. Max (weighted) flow methods do not work for matchings in general graphs.
Andy On Tue, Mar 18, 2014 at 9:31 AM, Jason Felice <jason.m.fel...@gmail.com>wrote: > I thought matching was a dual of max flow, so weighted matching was a dual > of min cost max flow (relabling edges with infinity minus cost). > > The simplest algorithm to implement would be Ford-Fulkerson with > Floyd-Warshall to find augmenting paths. The most efficient would be > Dinic's, I think? > > > > > On Tue, Mar 18, 2014 at 11:25 AM, Laurens Van Houtven <_...@lvh.cc> wrote: > >> Hi, >> >> >> On Tuesday, March 18, 2014 3:02:01 PM UTC+1, Paul deGrandis wrote: >> >>> I've written general versions of Blossom and Blossom V in the past, and >>> every so often a similar question comes up on this mailing list. >>> >> >> I'm guessing that wasn't in clojure? :-( >> >> Do you happen to know what happens when you throw Blossom V at a graph >> that doesn't have a perfect matching? E.g. for my use case, hotel room >> pairing, there's a 1/2 chance the graph ends up having an odd number of >> nodes... IIUC it won't terminate, but you can detect that it won't, so then >> you can just give the best-effort solution anyway? >> >> >>> I'd personally love to see both algorithms contributed to Loom if OP is >>> up for the task. >>> >> >> I'm afraid I've got a convex optimization problem in terms of financial >> aid grant sizes to solve first before I can start writing that code :-) >> >> cheers >> lvh >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Clojure" group. >> To post to this group, send email to clojure@googlegroups.com >> Note that posts from new members are moderated - please be patient with >> your first post. >> To unsubscribe from this group, send email to >> clojure+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en >> --- >> You received this message because you are subscribed to the Google Groups >> "Clojure" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to clojure+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/d/optout. >> > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
