SCIRP Mobile Website
Paper Submission

Why Us? >>

  • - Open Access
  • - Peer-reviewed
  • - Rapid publication
  • - Lifetime hosting
  • - Free indexing service
  • - Free promotion service
  • - More citations
  • - Search engine friendly

Free SCIRP Newsletters>>

Add your e-mail address to receive free newsletters from SCIRP.

 

Contact Us >>

WhatsApp  +86 18163351462(WhatsApp)
   
Paper Publishing WeChat
Book Publishing WeChat
(or Email:book@scirp.org)

Article citations

More>>

Gouveia, L., Simonetti, L. and Uchoa, E. (2011) Modeling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs. Mathematical Programming, 128, 123-148.
http://dx.doi.org/10.1007/s10107-009-0297-2

has been cited by the following article:

  • TITLE: Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

    AUTHORS: Miklos Molnar

    KEYWORDS: Multicast Routing, Quality of Service, Multi-Constrained Steiner Problem, Hierarchy, Partial Minimum Spanning Hierarchy, Branch and Bound

    JOURNAL NAME: Journal of Computer and Communications, Vol.4 No.14, November 15, 2016

    ABSTRACT: The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.