Artikel
Algorithms for the minimum spanning tree problem with resource allocation
We formulate the minimum spanning tree problem with resource allocation (MSTRA) in two ways, as discrete and continuous optimization problems (d-MSTRA/c-MSTRA), prove these to be NP-hard, and present algorithms to solve these problems to optimality. We reformulate d-MSTRA as the knapsack constrained minimum spanning tree problem, and solve this problem using a previously published branch-and-bound algorithm. By applying a ‘peg test', the size of d-MSTRA is (significantly) reduced. To solve c-MSTRA, we introduce the concept of f-fractionalsolution, and prove that an optimal solution can be found within this class of solutions. Based on this fact, as well as conditions for ‘pruning' subproblems, we develop an enumerative algorithm to solve c-MSTRA to optimality. We implement these algorithms in ANSI C programming language and, through extensive numerical tests, evaluate the performance of the developed codes on various types of instances.
- Language
-
Englisch
- Bibliographic citation
-
Journal: Operations Research Perspectives ; ISSN: 2214-7160 ; Volume: 3 ; Year: 2016 ; Pages: 5-13 ; Amsterdam: Elsevier
- Classification
-
Wirtschaft
- Subject
-
Minimum spanning tree problem
Resource allocation
Trade-off analysis
Branch-and-bound method
- Event
-
Geistige Schöpfung
- (who)
-
Kataoka, Seiji
Yamada, Takeo
- Event
-
Veröffentlichung
- (who)
-
Elsevier
- (where)
-
Amsterdam
- (when)
-
2016
- DOI
-
doi:10.1016/j.orp.2015.12.001
- Handle
- Last update
-
10.03.2025, 11:42 AM CET
Data provider
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
Object type
- Artikel
Associated
- Kataoka, Seiji
- Yamada, Takeo
- Elsevier
Time of origin
- 2016
Other Objects (12)
Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
Weight-Constrained Minimum Spanning Tree Problem
Engineering an external memory minimum spanning tree algorithm
A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems
Ant colony optimization and the minimum spanning tree problem
Minimum Spanning Trees Made Easier Via Multi-Objective Optimization
On the complexity of the bilevel minimum spanning tree problem
Bounded degree spanning trees
Inferring phylogenetic trees under the general Markov model via a minimum spanning tree backbone
Contagion pattern identification through minimum spanning trees during the Asian financial crisis
Erweiterung des Spanning Tree Simulators
Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
Weight-Constrained Minimum Spanning Tree Problem
Engineering an external memory minimum spanning tree algorithm
A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems
Ant colony optimization and the minimum spanning tree problem
Minimum Spanning Trees Made Easier Via Multi-Objective Optimization
On the complexity of the bilevel minimum spanning tree problem
Bounded degree spanning trees
Inferring phylogenetic trees under the general Markov model via a minimum spanning tree backbone
Contagion pattern identification through minimum spanning trees during the Asian financial crisis
Erweiterung des Spanning Tree Simulators
Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
Weight-Constrained Minimum Spanning Tree Problem
Engineering an external memory minimum spanning tree algorithm
A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems
Ant colony optimization and the minimum spanning tree problem
Minimum Spanning Trees Made Easier Via Multi-Objective Optimization
On the complexity of the bilevel minimum spanning tree problem
Bounded degree spanning trees
Inferring phylogenetic trees under the general Markov model via a minimum spanning tree backbone
Contagion pattern identification through minimum spanning trees during the Asian financial crisis
Erweiterung des Spanning Tree Simulators