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⁵).

Full Document (PDF)

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",
    url = "https://publications.info.uaic.ro/technical-reports/archive/tr13-02-2013-a-simple-push-relabel-algorithm-for-sub-modular-flows/"
}