Emanuel Olariu

In this paper we present a combinatorial push-relabel algorithm based on lowest level/bfs traversal for matroid optimization. In contrast with other known algorithms our procedure uses lowest level rule and needs no lexicographic order of the elements. Combined with a reduction of the number of active basis our strategy gives a time complexity of Ο(n6).

Full Document (PDF)

Bibtex

@TechReport{nspafmo,
    author = "Emanuel Olariu",
    title = "{A new strategy for push-relabel algorithm framework for matroid optimization}",
    institution = "``Al.I.Cuza'' University of Ia{c s}i, Faculty of Computer Science",
    year = "2013",
    number = "TR 13-01",
    url = "https://publications.info.uaic.ro/technical-reports/archive/tr13-01-2013-a-new-strategy-for-push-relabel-algorithm-framework-for-matroid-optimization/"
}