Network reinforcement

• 成果类型: Article; Proceedings Paper
• 署名作者: Barahona, F
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0648-6
• 发表日期: 2006
• 页码: 181-200
• 关键词: faster algorithm; minimum cuts; strength

摘要

We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invulnerability of a network. Our algorithm has the same asymptotic complexity as vertical bar V vertical bar applications of the minimum cut algorithm of Goldberg & Tarjan.