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



Abstract

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}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!