ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Relative Merits of Minimum Cost Spanning Trees and Steiner Trees

Journal: International Journal of Science and Research (IJSR) (Vol.3, No. 5)

Publication Date:

Authors : ; ;

Page : 236-239

Keywords : HMSTP(Minimum Spanning Tree Problem); Subtrees; MBST(Minimum Botteleneck Spanning Tree); DMSTP(Diameter-Constrained Minimum Spanning Tree);

Source : Downloadexternal Find it from : Google Scholarexternal


This paper discusses about the concepts of Minimum cost spanning tree and what happens if it is used in place of Steiner tree. We show that the MSTP is equivalent to a Steiner Tree Problem (STP) in an adequate layered graph. We also adapt the proposed approach for the Diameter-Constrained Minimum Spanning Tree Problem (DMSTP). Although the HMSTP and the DMSTP have symmetric edge costs, we will focus on so-called directed formulations.

Last modified: 2014-07-01 19:18:54