Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization (Q847846)

The authors study the problem of minimizing bisubmodular functions. They begin by presenting a history of bisubmodularity, its importance and an overview of the algorithms for solving this class of problems. In the second section, the preliminary definitions necessary for this problem are presented, followed by a series of theorems describing the existing approaches. The third and main section contains, in a lot of detail, the proposed strongly polynomial bisubmodular function minimization algorithm, including running time estimates. The article concludes with potential extensions to the algorithm, a list of open questions and a large number of relevant references.