Il problema dell'albero ricoprente di costo minimo con grado limitato.

Given a graph G= (V, E), the search for its minimum cost spanning tree with bounded degree is a problem that is probably not solvable in polynomial time. The difficulty is to be able to satisfy the degree upper bound imposed on each vertex. In 1994, Fürer and Raghavachari presented a polynomial algorithm to find a spanning tree violating the degree bound by at most one. This algorithm essentially represents the best possible solution to the problem that is presented in this thesis.

Dato un grafo G= (V, E) la ricerca di un suo albero ricoprente di costo minimo con grado limitato, risulta essere un problema molto probabilmente non risolvibile in tempo polinomiale. La difficoltà è quella di riuscire a soddisfare il limite superiore imposto sul grado di ogni vertice. Nel 1994, gli studiosi Fürer and Raghavachari hanno presentato un algoritmo polinomiale con il quale si trova un albero ricoprente in cui il grado di ogni vertice viola quello fissato al massimo di un’unità. Tale algoritmo rappresenta sostanzialmente la migliore soluzione possibile al problema presentato in questa tesi.