A distributed algorithm for a maximal 2-packing set in Halin graphs
| Autor: | José Alberto Fernández-Zepeda, Alejandro Flores-Lamas, Joel Antonio Trejo-Sánchez |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
Computer Networks and Communications Computer science 020206 networking & telecommunications 02 engineering and technology Graph Theoretical Computer Science Vertex (geometry) Combinatorics Artificial Intelligence Hardware and Architecture Distributed algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Time complexity Software MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Parallel and Distributed Computing. 142:62-76 |
| ISSN: | 0743-7315 |
| DOI: | 10.1016/j.jpdc.2020.03.016 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect