A distributed algorithm for a maximal 2-packing set in Halin graphs

Abstract In this work, we propose Maximal-2-Packing-Halin , a distributed algorithm that finds a maximal 2-packing set in undirected non-geometric Halin graphs of order n in linear time. First, this algorithm finds an external face of the input graph through the application of graph-reduction rules. Second, each vertex determines if it belongs to a maximal 2-packing set by applying a set of vertex-coloring rules.