Blocking optimal arborescences
成果类型：
Article
署名作者：
Bernath, Attila; Pap, Gyula
署名单位：
Eotvos Lorand University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-016-1025-3
发表日期：
2017
页码：
583-601
关键词：
摘要：
The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph with a designated root node and arc-costs , find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give solves a weighted version as well, in which a nonnegative weight function (unrelated to c) is also given, and we want to find a subset H of the arc set such that H intersects every minimum c-cost r-arborescence, and is minimum. The running time of the algorithm is , where n and m denote the number of nodes and arcs of the input digraph, and T(n, m) is the time needed for a minimum cut computation in this digraph. A polyhedral description is not given, and seems rather challenging.
来源URL：