TR13-01 (2013) – A New Strategy for Push-Relabel Algorithm Framework for Matroid Optimization

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 Ο(n⁶).

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",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"
}