کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10347361 699186 2005 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Heuristic and exact algorithms for the spanning tree detection problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Heuristic and exact algorithms for the spanning tree detection problem
چکیده انگلیسی
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 α.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 32, Issue 2, February 2005, Pages 239-255
نویسندگان
, , ,