Date: Thu, 13 Feb 86 09:26 EST
From:: elisha
Subject: seminar notice
To: *mac@MIT-MC.ARPA

                    	   Friday, February 14, 1985
			      12:00 noon - Lecture
			   12:02 p.m. - Refreshments
			 Room NE43 - 8th Floor Playroom

			  BONNY DORR and DAVE BRAUNEGG
		       Artificial Intelligence Laboratory
			       MIT, Cambridge, MA

		    "A New Approach to the Max-Flow Problem"

    The Maximum Flow problem has many applications in the fields of
    combinatorics and digestion research.  In this seminar, the flow around
    a standardized GSL table will be described.  Audience participation is
    considered a crucial part of the seminar.  The first algorithm for the
    problem was discovered in 1956 by Lea and Perkins, and a number of
    algorithms have been proposed since then.  However,all previously known
    max-flow algorithms worked by finding alimentary paths, either one path
    at a time or all shortest alimentary paths at once (by using the level
    range technique of B. Crocker).
						   3   5/3  2/3
    The previously known algorithms give an O(min(n , n    m    nm log n))
    upper bound on the problem; the upper bound is achieved by a combination
    of three algorithms due to Beard, Childs, and Rombauer.  The only
    previously known parallel max-flow algorithm, due to Duncan & Hines,
    runs in parallel
	    2
    time O(n log n) and requires omega (n) hands for each edge of the table.

    We propose a method for computing max-flow without finding alimentary
    paths explicitly.  A sequential algorithm based on this method runs in
    time
	       2
    O(nm log (n /m))).  This bound is better than the previously known bound, and
    it is achieved by a single algorithm.  A parallel algorithm based on the method
		    2
    runs in time O(n log n) using a constant number of hands per edge of the
    table; this makes the implementation of the algorithm much more feasible
    (compared to the Duncan & Hines algorithm).