Decomposition methods based on articulation vertices for degree-dependent spanning tree problems
| Autor: | Jose L. Sainz-Pardo, Mercedes Landete, Alfredo Marín |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
021103 operations research Control and Optimization Trémaux tree Spanning tree Applied Mathematics Shortest-path tree 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Minimum spanning tree k-minimum spanning tree 01 natural sciences Combinatorics Distributed minimum spanning tree Computational Mathematics 010201 computation theory & mathematics Euclidean minimum spanning tree Minimum degree spanning tree Mathematics |
| Zdroj: | Computational Optimization and Applications. 68:749-773 |
| ISSN: | 1573-2894 0926-6003 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|