[informatik-bonn] O(Dinic)

  • From: Lutz Oberst <oberst@xxxxxxxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sun, 9 Feb 2003 14:09:42 +0100

Hallo,

ich verstehe nicht ganz, warum Dinic eine Laufzeit von O(n^2m)
hat.

Phase 1: berechnung des geschichteten Netzes: mit BFS in O(m+n)
Phase 2: BFS für P(s,t): O(m+n)
Phase 3: Augmentieren des Pfades: O(n)

Wobei 1+2 maximal n mal ausgeführt werden müssen.

Damit: O(m+n) + n * O(m+2n) = O(m+n)+O(nm+n^2) = O(nm + n^2) = O(n^2)

Wo ist da der Fehler?

Bye, Lutz
-- 
"We left all that stuff out. If there's an error, we have this routine
 called panic, and when it is called, the machine crashes, and you
 holler down the hall, 'Hey, reboot it.'"
        -- Dennis Ritchie about error code handling in UNIX.


Other related posts:

  • » [informatik-bonn] O(Dinic)