|
In 1998, Hu and Liu developed a strongly polynomial algorithm for solving the inverse arborescence problem that aims at modifying minimally a given cost-function on the edge-set of a digraph so that an input arborescence becomes a cheapest one. In this note, we develop a conceptually simpler algorithm along with a min-max theorem for the minimum modification of the cost-function. The approach is based on a link to a min-max theorem and a two-phase greedy algorithm by the first author from 1979 concerning the primal optimization problem of finding a cheapest subgraph of a digraph that covers an intersecting family along with the corresponding dual optimization problem, as well.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s and Hajdu, Gergely}, |
| TITLE | = | {Simple algorithm and min-max formula for the inverse arborescence problem}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-15} |