TR13-02 (2013) – A simple push-relabel algorithm for sub-modular flows

Cristian Frasinaru, Emanuel Olariu

In this paper we present a combinatorial push-relabel algorithm for sub-modular flows. Ourprocedure, using a lowest level rule combined with a bfs-like traversal, needs no lexicographic orderof the elements, and gives a time complexity of Ο(n⁵).

Bibtex

@TechReport{sprasmf,
author = "Cristian Frasinaru and Emanuel Olariu ",
title = "{A simple push-relabel algorithm for sub-modular flows}",
institution = "``Al.I.Cuza'' University of Ia{c s}i, 
                 Faculty of Computer Science",
year = "2013",
number = "TR 13-02",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"
}