Design of interconnection of local area networks

This paper addresses the interconnection of local area networks (LANs) using bridges. The interconnection problem is difficult to solve and feasible solutions are usually obtained through heuristics. The description of a simplified approach to solve the problem of interconnecting LANs is followed by the formulation of the problem and the development of a Lagrangean relaxation. A Tabu search metaheuristic for designing minimum cost spanning tree topologies is also presented. Computational results are given for the interconnection of up to ten local area networks.