A constrained minimum spanning tree problem

Alberto Peretti

No 08/2018, Working Papers from University of Verona, Department of Economics

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.

Keywords: Graph theory; Trees; Minimum spanning tree problem; Constrained minimum spanning trees (search for similar items in EconPapers)
JEL-codes: C65 C69 (search for similar items in EconPapers)
Date: 2018-12
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dse.univr.it/home/workingpapers/wp2018n8.pdf First version (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ver:wpaper:08/2018

Access Statistics for this paper

More papers in Working Papers from University of Verona, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Michael Reiter ().