Blocking optimal k-arborescences

DOI10.1137/1.9781611974331.CH115MaRDI QIDQ4575699zbMATH OpenOpenAlexFDO

Authors Attila Bernáth, Tamás Király

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.04207

zbMATH Keywords

coveringmatroidspolynomial-time algorithmsarborescences

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: Given a digraph $D=(V,A)$ and a positive integer $k$, an arc set $FsubseteqA$ is called a extbf{$k$-arborescence} if it is the disjoint union of $k$ spanning arborescences. The problem of finding a minimum cost $k$-arborescence is known to be polynomial-time solvable using matroid intersection. In this paper we study the following problem: find a minimum cardinality subset of arcs that contains at least one arc from every minimum cost $k$-arborescence. For $k=1$, the problem was solved in [A. Bern'ath, G. Pap , Blocking optimal arborescences, IPCO 2013]. In this paper we give an algorithm for general $k$ that has polynomial running time if $k$ is fixed.

Recommendations

• Blocking unions of arborescences
• scientific article; zbMATH DE number 1420748
• scientific article; zbMATH DE number 7692724

Cited in

(10)

• Robustness of minimum cost arborescences
• Blocking unions of arborescences
• The \(b\)-branching problem in digraphs
• Minimum k arborescences with bandwidth constraints
• Blocking optimal structures
• scientific article; zbMATH DE number 7692724 (Why is no real title available?)
• scientific article; zbMATH DE number 1420748 (Why is no real title available?)
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• Packing of arborescences with matroid constraints via matroid intersection
• scientific article; zbMATH DE number 7378329 (Why is no real title available?)

This page was built for publication: Blocking optimal \(k\)-arborescences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575699)