In the classical general framework of the minimum spanning tree problem for a weighted graph we consider the case in which a predetermined vertex has a certain fixed degree. In other words, given a weighted graph G, one of its vertices v0 and a positive integer k, we consider the problem of finding the minimum spanning tree of G in which the vertex v0 has degree k, that is the number of edges coming out of v0. We recall that among the various methods for the solution of the unconstrained problem an efficient way to find the minimum spanning tree is based on the simple procedure of choosing one after the other an edge of minimum weight that has not be chosen yet and does not create cycles if added to the previously chosen edges. This technique is known as the “greedy algorithm”. There are problems for which the greedy algorithm works and problems for which it does not. We prove that for the solution of the one degree constrained minimum spanning tree problem the classical greedy algorithm finds a right solution.

### A constrained minimum spanning tree problem

#### Abstract

In the classical general framework of the minimum spanning tree problem for a weighted graph we consider the case in which a predetermined vertex has a certain fixed degree. In other words, given a weighted graph G, one of its vertices v0 and a positive integer k, we consider the problem of finding the minimum spanning tree of G in which the vertex v0 has degree k, that is the number of edges coming out of v0. We recall that among the various methods for the solution of the unconstrained problem an efficient way to find the minimum spanning tree is based on the simple procedure of choosing one after the other an edge of minimum weight that has not be chosen yet and does not create cycles if added to the previously chosen edges. This technique is known as the “greedy algorithm”. There are problems for which the greedy algorithm works and problems for which it does not. We prove that for the solution of the one degree constrained minimum spanning tree problem the classical greedy algorithm finds a right solution.
##### Scheda breve Scheda completa Scheda completa (DC) 2018
Graph theory, Trees, Minimum spanning tree problem, Constrained minimum spanning trees
File in questo prodotto:
File
wp2018n8.pdf

accesso aperto

Descrizione: Articolo scientifico
Tipologia: Documento in Pre-print
Licenza: Dominio pubblico
Dimensione 382.52 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11562/1012676`
• ND
• ND
• ND