کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10347361 | 699186 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Heuristic and exact algorithms for the spanning tree detection problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: Computers & Operations Research - Volume 32, Issue 2, February 2005, Pages 239-255
نویسندگان
Takeo Yamada, Seiji Kataoka, Kohtaro Watanabe,