Algorithms for the minimum spanning tree problem with resource allocation

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...

Full description

Bibliographic Details
Main Authors: Seiji Kataoka, Takeo Yamada
Format: Article
Language:English
Published: Elsevier 2016-01-01
Series:Operations Research Perspectives
Subjects:
Minimum spanning tree problem
Resource allocation
Trade-off analysis
Branch-and-bound method
Online Access:http://www.sciencedirect.com/science/article/pii/S2214716016000026

Internet

http://www.sciencedirect.com/science/article/pii/S2214716016000026

Similar Items