Heuristic and exact algorithms for the spanning tree detection problem

Heuristic and exact algorithms for the spanning tree detection problem

0.00 Avg rating0 Votes
Article ID: iaor20052277
Country: United Kingdom
Volume: 32
Issue: 2
Start Page Number: 239
End Page Number: 255
Publication Date: Feb 2005
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics, optimization
Abstract:

Given an integer α and an undirected graph with edges associated with integer weights, the spanning tree detection problem (STDP) is to find, if one exists, a spanning tree of weight α. STDP is NP-hard. In this paper we develop both approximate and exact algorithms to solve STDP. Approximate algorithm consists of a greedy method to construct an initial spanning tree quickly, and a local search method that improves the weight of the tree successively toward α. To solve STDP completely, we take a ‘divide and conquer’ approach and develop an exact algorithm. These algorithms are implemented in C language and we conduct some numerical tests to evaluate the performance of the developed algorithms for various types and sizes of instances. In most cases, we are able to solve STDPs with up to 1000 nodes in less than a few seconds. Moreover, to solve harder instances we try tabu search as well, and mention how the developed algorithm can be modified to list up all the spanning trees of weight α.

Reviews

Required fields are marked *. Your email address will not be published.