The Constrained Out-degree Minimum K-arborescence Problem

In this thesis,we mainly consider the constrained out-degree minimum K-arborescence problem, which is defuned as follows:given a weighted digraph D=(V, A; w) with n+1vertices and m arcs, where w:Aâ†'R+, we are asked to find a subset H of n+K arcs in D so that the subgraph D[H] induced by H has a spanning arborescence with a fixed root, and the out-degree of fixed root is a constant, and D[H] contain no directed cycles, the objective is to minimize the total weight of arcs in H.In this thesis, we decompose the constrained out-degree minimum K-arboresce-nce problem into the constrained out-degree minimum arborescence problem and the minimum K-arborescence problem.we present a polynomial-time algorithm to solve the constrained out-degree minimum arborescence problem, whose com-plexity is O(n3m). We design a polynomial-time algorithm to solve the minimum K-arborescence problem, whose complexity is O(m2lgm). By combining the strat-egy of two algorithm design above, we give a polynomial-time algorithm to solve the constrained out-degree minimum K-arborescence problem, whose complexity is O(n3m).