Decomposition methods based on articulation vertices for degree-dependent spanning tree problems

Mercedes Landete (), Alfredo Marín and José Luis Sainz-Pardo
Additional contact information
Mercedes Landete: Universidad Miguel Hernandez de Elche
Alfredo Marín: Universidad de Murcia
José Luis Sainz-Pardo: Universidad Miguel Hernandez de Elche

Computational Optimization and Applications, 2017, vol. 68, issue 3, No 13, 749-773

Abstract: Abstract Decomposition methods for optimal spanning trees on graphs are explored in this work. The attention is focused on optimization problems where the objective function depends only on the degrees of the nodes of the tree. In particular, we deal with the Minimum Leaves problem, the Minimum Branch Vertices problem and the Minimum Degree Sum problem. The decomposition is carried out by identifying the articulation vertices of the graph and then its blocks, solving certain subproblems on the blocks and then bringing together the optimal sub-solutions following adequate procedures. Computational results obtained using similar Integer Programming formulations for both the original and the decomposed problems show the advantage of the proposed methods on decomposable graphs.

Keywords: Integer Programming; Spanning tree; Articulation vertex; Block-cutpoint graph (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-017-9924-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:coopap:v:68:y:2017:i:3:d:10.1007_s10589-017-9924-7

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-017-9924-7

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().