Computational results for Constrained Minimum Spanning Trees in Flow Networks

Dalila B. M. M. Fontes ()
Additional contact information
Dalila B. M. M. Fontes: Faculdade de Economia da Universidade do Porto, Portugal

FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto

Abstract: In this work, we address the problem of finding a minimum cost spanning tree on a single source flow network. The tree must span all vertices in the given network and satisfy customer demands at a minimum cost. The total cost is given by the summation of the arc setup costs and of the nonlinear flow routing costs over all used arcs. Furthermore, we restrict the trees of interest by imposing a maximum number of arcs on the longest arc emanating from the single source vertex. We propose a dynamic programming model an solution procedure to solve this problem exactly. Intensive computational experiments were performed using randomly generated test problems and the results obtained are reported. From them we can conclude that the method performance is independent of the type of cost functions considered and improves with the tightness of the constrains.

Keywords: Dynamic programming; network flows; constrained trees; general nonlinear costs (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 17 pages
Date: 2007-06
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/07.06.12_WP243_DalilaFontes.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.fep.up.pt/investigacao/workingpapers/07.06.12_WP243_DalilaFontes.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/07.06.12_WP243_DalilaFontes.pdf)

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:por:fepwps:243

Access Statistics for this paper

More papers in FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto Contact information at EDIRC.
Bibliographic data for series maintained by ().