A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler

In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location pr...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2017-12, Vol.28 (8), p.1021-1045
Main Authors: Trejo-Sánchez, Joel Antonio, Fernández-Zepeda, José Alberto, Ramírez-Pacheco, Julio César
Format: Article
Language:English
Subjects:
Algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length O ( log n ) bits. The execution time of this algorithm is O ( n ) rounds or O ( n 2 ) time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.
ISSN:0129-0541
1793-6373
DOI:10.1142/S012905411750037X