Published in:
Blocking Optimal Arborescences, Proc. IPCO '13, Lecture Notes in Computer Science Volume 7801, 2013, pp 74-85
Given a digraph $D=(V,A)$ with a designated root node $r\in V$ and
arc-costs $c:A\to {\mathbb R}$, we consider the problem of finding a minimum
cardinality subset $H$ of the arc set $A$ such that $H$ intersects every
minimum cost $r$-arborescence.
We give a polynomial algorithm for finding such an arc set
$H$. The algorithm solves a weighted version as well, in which a
nonnegative weight function $w:A\to {\mathbb R}_+$ is also given, and we
want to find a subset $H$ of the arc set such that $H$ intersects
every minimum cost $r$-arborescence, and $w(H)$ is minimum.
A revised and extended version of this report is available as report no. 2015-06.
Bibtex entry:
@techreport{egres-11-13,
AUTHOR | = | {Bern{\'a}th, Attila and Pap, Gyula}, |
TITLE | = | {Covering minimum cost arborescences}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2011}, |
NUMBER | = | {TR-2011-13} |