Title:

Determining hop-constrained spanning trees with repetitive heuristics, Journal of Telecommunications and Information Technology, 2007, nr 4

Creator:

Voß, Stefan ; Gouveia, Luis ; Fernandes, Manuela

Subject and Keywords:

metaheuristics ; hop-constrained spanning tree problem ; pilot method ; rollout method

Description:

The hop-constrained minimum spanning tree problem is the problem of determining a rooted spanning tree of minimum cost in which each path from the root node to any other node contains at most H hops or edges. This problem relates to the design of centralized tree networks with quality of service requirements (in telecommunications) and has a close relation with other tree problems. In this paper we investigate the adaptation of some well-known “repetitive” heuristics used for the capacitated minimum spanning tree problem to the hop-constrained minimum spanning tree problem and investigate some simple look ahead mechanisms for enhancing the quality of a savings heuristic. Computational results for a set of benchmark tests with up to 80 nodes are presented.

Publisher:

Instytut Łączności - Państwowy Instytut Badawczy, Warszawa

Date:

2007, nr 4

Resource Type:

artykuł

Format:

application/pdf

DOI:

10.26636/jtit.2007.4.846

ISSN:

1509-4553

eISSN:

1899-8852

Source:

Journal of Telecommunications and Information Technology

Language:

ang

Rights Management:

Biblioteka Naukowa Instytutu Łączności