Given a graph @math , @math , we wish to compute a spanning tree whose maximum vertex degree is as small as possible. Computing the exact optimal solution is known to be NP-hard, since it generalizes the Hamiltonian path problem. For the approximation version of this problem, a @math time algorithm that computes a spanning tree of degree at most @math is previously known [F "urer, Raghavachari 1994]; here @math denotes the optimal tree degree. In this paper we give the first near-linear time algorithm for this problem. Specifically speaking, we first propose a simple @math time algorithm that achieves an @math approximation; then we further improve this algorithm to obtain a @math approximation in @math time.
Another variant is minimum degree Steiner trees which is related to network broadcasting @cite_12 @cite_3 @cite_11 . For undirected graphs, authors of @cite_1 showed that the same approximation guarantee and running time can be achieved as with minimum degree spanning trees in undirected graphs, i.e., a solution of tree degree @math and a running time of @math . For the directed case, @cite_11 showed that directed minimum degree Steiner trees problem cannot be approximated within @math unless @math , where @math is the set of terminals.
@cite_3 @cite_1 @cite_12 @cite_11
2002764437 2066700938 1918603512
We study network-design problems with multiple design objectives. In particular, we look at two cost measures to be minimized simultaneously: the total cost of the network and the maximum degree of any node in the network. Our main result can be roughly stated as follows: given an integer @math , we present approximation algorithms for a variety of network-design problems on an @math -node graph in which the degree of the output network is @math and the cost of this network is @math times that of the minimum-cost degree- @math -bounded network. These algorithms can handle costs on nodes as well as edges. Moreover, we can construct such networks so as to satisfy a variety of connectivity specifications including spanning trees, Steiner trees and generalized Steiner forests. The performance guarantee on the cost of the output network is nearly best-possible unless @math . We also address the special case in which the costs obey the triangle inequality. In this case, we obtain a polynomial-time approximation algorithm with a stronger performance guarantee. Given a bound @math on the degree, the algorithm finds a degree- @math -bounded network of cost at most a constant time optimum. There is no algorithm that does as well in the absence of triangle inequality unless @math . We also show that in the case of spanning networks, we can simultaneously approximate within a constant factor yet another objective: the maximum cost of any edge in the network, also called the bottleneck cost of the network. We extend our algorithms to find TSP tours and @math -connected spanning networks for any fixed @math that simultaneously approximate all these three cost measures. Abstract The problem of constructing a spanning tree for a graph G = ( V , E ) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D ⊆ V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D . Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time. Given an undirected graph representing a network of processors, and a source node containing a message that must be broadcast to all the nodes, find a scheme that accomplishes the broadcast in the minimum number of time steps. At each time step, any processor that has received the message is allowed to communicate the message to at most one of its neighbors in the network, i.e. can communicate via a telephone call to a neighbor. This has been termed the minimum broadcast time problem under the telephone model and is known to be NP-complete. The minimum broadcast time in a graph is closely related to the poise of the graph. The poise of a tree is defined to be the quantity (maximum degree of any node in the tree+diameter of the tree). The poise of a graph is the minimum poise of any of its spanning trees. Computing the poise of a graph is shown to be NP-hard and an algorithm for computing a spanning tree of approximately minimum poise is derived. This algorithm is then used to derive an O(log sup 2 n log log n)-approximation for the minimum broadcast time problem on an n-node graph. Our algorithm extends to many generalizations of the problem such as the multicast problem, a telephone model allowing conference calls, and to the closely related minimum gossip time problem. >