A Heuristic Algorithm for Solving Steiner Tree Problem on Urban Traffic Network

سال انتشار: 1391
محل انتشار: بیستمین کنفرانس مهندسی برق ایران
کد COI اختصاصی: ICEE20_200
زبان مقاله: انگلیسی
تعداد مشاهده: 1897

نویسندگان

Department of Computer Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

چکیده

The Steiner tree problem connects a subset of given nodes called terminals that this connection is absolutely a tree and it has the minimum cost. In this tree due to the reduction ofcost of path, some non-terminal nodes are used, which called Steiner nodes. The Steiner tree problem has various usagesthat one of them is routing in the urban traffic networks. In such networks with a large amount of nodes and edges, finding the optimum path which connects small amounts of terminals isdesired. Since these problems usually have wide scales, we should use heuristic algorithms, which find the near optimumSteiner tree in polynomial time. In this paper, a heuristic algorithm is proposed that needs O ( ( + log )). Thealgorithm finds the near optimum answer of Steiner tree on the given graph. The results of investigations show that this algorithm finds more accurate answers in comparison to theprevious ones

کلیدواژه ها

Steiner tree, Heuristic Algorithm, Undirected weighted graph

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.