Um algoritmo aproximativo para o problema de árvore geradora minimizando excesso de grau

Abstract

The problem of obtaining a spanning tree is well-known and can be solved efficiently. However, even minor constraints makes the problem NP-hard (WU; CHAO, 2004). Many constraints to the problem have been presented in the literature and in particular, the problem of the minimum- degree spanning tree is emphasized. This is the problem of obtaining a spanning tree T of a graph G such that the maximum degree of T is the smallest among all the spanning trees obtained from G . It is easy to verify that this problem is NP-hard because when the maximum degree of T is two, T is equivalent to a hamiltonian path. In this work, a new approach is proposed for the problem of spanning tree with degree restriction, described as follows: Given a graph G and an integer d , we want to find a generating tree T whose sum of the degrees exceeds in each vertex (how much the degree of the vertex exceeds d ) in T is the smallest possible. In this way, an approximate algorithm is presented, which is compared to the algorithm described in (FURER; RAGHAVACHARI, 1994), an algorithm that minimizes the maximum degree of a spanning tree, and which has an intimate relationship with the approach proposed in this work. The comparisons are performed in relation to the mean of the sums and the response time returned by both algorithms.