This paper considers various forms of objective function that may be applied in the calculation of spanning trees in different network situations. Conventional link and path cost approaches are compared to those based on switch or bridge costs more appropriate for wireless applications. Variant objectives are formulated and compared. Although efficient exact algorithmic approaches exist only for the link cost objectives, reasonable approximations for the switch/bridge equivalents are to be found with simple greedy heuristics and better results still through various forms of iterated local search such as tabu search and simulated annealing.
Computer and Systems Architecture | Digital Communications and Networking | Hardware Systems | Systems and Communications
Morgan, M. & Grout, V. (2006), ‘Spanning Tree Objective Functions and Algorithms for Wireless Networks’. [Paper presented to the 2006 IEEE Sarnoff Symposium (Sarnoff 2006), 27-28 March 2006]. Princeton, New Jersey, USA: IEEE
Digital Commons Citation
Morgan, Mike J. and Grout, Vic, "Spanning Tree Objective Functions and Algorithms for Wireless Networks" (2006). Computing. Paper 73.