TR-2011-13

Covering minimum cost arborescences

Attila Bernáth, Gyula Pap

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2011},
NUMBER	=	{TR-2011-13}

}