Support Requests item #1445526, was opened at 2006-03-08 11:16 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1445526&group_id=7586 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Vincenzo Failla (vfailla) Assigned to: Nobody/Anonymous (nobody) Summary: Max Flow Algorithm Initial Comment: Hi, I'm a student in Computer Science and Telecommunications. I'm working for my thesis job on graph algorithms and I'm developping a code for the k-cut and the multiterminal cut problem. To calculate max flow/minimum s-t cut, I used the Goldberg algorithm implemented in the Boost Library. Now I like to have more information (f.e.: the complexity) about Goldberg Algorithm used in Boost Library. I already gave a look to references section of Boost Project but I had some difficult to find the related Goldberg article ("A New Max-Flow Algorithm", 1985). However in a later article ("A New Approach to the Maximum-Flow Problem", Goldberg and Tarjan 1986) a complexity of O(n^3) for the Goldberg algorithm (1985) is given. After simulation tests, I think the algorithm implemented in Boost Library has lower complexity than O(n^3). Is this possible? Is there someone has the Goldberg article (1985)? I will be grateful if someone can help me. Thanks ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1445526&group_id=7586 ------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ Boost-bugs mailing list Boost-bugs@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs