The Pseudo-arborescence Construction Problem

In this thesis,according to the practical problem of broadband in real literature,we consider the pseudo-arborescence construction problem.First,we give a definition of the pseudo-arborescence,propose the minimum pseudo-arborescence problem,and re-fer the broadband problem to the pseudo-arborescence construction problem.We design a polynomial-time algorithm to solve the minimum pseudo-arborescence problem,the time complexity of this algorithm is O(n3).Second,we propose the pseudo-arborescence construction problem,it is a combination of the minimum pseudo-arborescence prob-lem and the bin-packing problem,we prove that the pseudo-arborescence construction problem is N P-complete and then design an asymptotic 7/4-approximation algorithm and the time complexity is O(n3).Finally,we consider the special case of the pseudo-arborescence construction problem,i.e.,c(e)= 0 for each arc e,we design an asymptotic 3/2-approximation algorithm to sovle this special case and the time complexity is also O(n3).