کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4962885 1364949 2017 8 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
Genetic algorithms to balanced tree structures in graphs☆
ترجمه فارسی عنوان
الگوریتم های ژنتیک برای ساختارهای درخت متعادل در نمودارها
کلمات کلیدی
درخت پوشای حداقل ؛ درخت کوتاه ترین مسیر؛ Spanner درخت؛ درخت پوشای متوازن ؛ درخت Spanning کششی حداکثر حداقل؛ الگوریتم ژنتیک؛
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی

Given an edge-weighted graph G=(V,E) with vertex set V and edge set E, we study in this paper the following related balanced tree structure problems in G. The first problem, called Constrained Minimum Spanning Tree Problem (CMST), asks for a rooted tree T in G that minimizes the total weight of T such that the distance between the root and any vertex v in T is at most a given constant C times the shortest distance between the two vertices in G. The Constrained Shortest Path Tree Problem (CSPT) requires a rooted tree T in G that minimizes the maximum distance between the root and all vertices in V such that the total weight of T is at most a given constant C times the minimum tree weight in G. The third problem, called Minimum Maximum Stretch Spanning Tree (MMST), looks for a tree T in G that minimize the maximum distance between all pairs of vertices in V. It is easy to conclude from the literatures that the above problems are NP-hard. We present efficient genetic algorithms that return (as shown by our experimental results) high quality solutions for these problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Swarm and Evolutionary Computation - Volume 32, February 2017, Pages 132-139
نویسندگان
, ,