Title: Two phased heuristic algorithm for capacitated minimal spanning tree networks

Authors: Yong-Jin Lee

Addresses: Department of Computer Science, Woosong University, Jayang-Dong, Dong-Ku, Taejon 300-100, Korea

Abstract: Modern computer networks consist of backbone networks and local access networks. Typical local area networks (LANs) can be defined as end-user-nodes of the local access networks. The problem is composed of finding the best way to link nodes to a central node site and, in graph-theoretical terms, it is to determine a minimal spanning tree with a capacity constraint (CMST). In this paper, a heuristic algorithm with two phases is presented. Computational experience confirms that our algorithm improves the solutions achieved by the existing algorithm and requires the relatively short running time. The algorithm can be applied to design of local area network in an organisation or centralised network.

Keywords: topological design; computer networks; capacitated minimum spanning tree; heuristic algorithms; LAN design; local area networks; capacity constraints.

DOI: 10.1504/IJCAT.2005.007207

International Journal of Computer Applications in Technology, 2005 Vol.24 No.2, pp.61 - 67

Published online: 23 Jun 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article