کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431751 688623 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
ترجمه فارسی عنوان
الگوریتم توزیع شده برای حداکثر 2 بسته بندی در نمودار بیرونی هندسی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We propose a distributed algorithm for the maximal 2-packing set in a geometric outerplanar graph.
• The execution time of this algorithm is O(n)O(n) steps.
• The algorithm has three phases: leader election, graph exploration, and vertex coloring.
• The vertex coloring phase resembles an ear decomposition of the input graph.
• When the input graph is a ring, the algorithm computes the maximum 2-packing set.

In this paper, we present a deterministic distributed algorithm that computes the maximal 2-packing set in a geometric outerplanar graph. In a geometric outerplanar graph, all the vertices have location coordinates in the plane and lie on the boundary of the graph. Our algorithm consists of three phases. First, it elects a vertex as the leader. Second, it explores the graph to determine relevant information about the structure of the input graph. Third, with this information, it computes a maximal 2-packing set. When the input graph is a ring, the algorithm computes a maximum 2-packing set. The execution time of this algorithm is O(n)O(n) steps and it uses O(nlogn)O(nlogn) messages. This algorithm does not require knowledge of the size of the input graph. To the best of our knowledge, this is the first deterministic distributed algorithm that solves such a problem for a geometric outerplanar graph in a linear number of steps.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 74, Issue 3, March 2014, Pages 2193–2202
نویسندگان
, ,