A Self-Stabilizing Algorithm for Constructing ST-Reachable Directed Acyclic Graph When lS| ≤ 2 and |T| ≤ 2

• Main Authors: Kim, Yonghwan, Shibata, Masahiro, Sudo, Yuichi, Nakamura, Junya, Katayama, Yoshiaki, Masuzawa, Toshimitsu
• Format: Conference Proceeding
• Language: English
• Subjects: a directed acyclic graph; an ST-reachable DAG; Computational modeling; Directed acyclic graph; Internet of Things; Routing; Schedules; self-stabilization; Wireless networks
• ISSN: 2575-8411
• DOI: 10.1109/ICDCS.2019.00219

In this paper, we introduce a new graph structure named an ST-reachable directed acyclic graph which is a directed acyclic graph (DAG) that guarantees reachability from every sender to every target (i.e., a directed path exists). When an arbitrary connected undirected graph G=(V,E) and two sets of the vertices, senders S (⊂ V) and targets T (⊂ V), are given, we consider construction of a minimal ST-reachable DAG by changing some undirected edges to arcs and removing the remaining edges. This implies that every node in T is reachable from every node in S on the constructed ST-reachable DAG. In particular, our goals are (1) to find the necessary and sufficient condition that an ST-reachable DAG can be constructed, and (2) to design a self-stabilizing algorithm for constructing a minimal ST-reachable DAG (if exists). In this paper, we present the necessary and sufficient condition that a minimal ST-reachable DAG can be constructed when S ≤ 2 and |T| ≤ 2, and propose a self-stabilizing algorithm to construct an ST-reachable DAG (if exists) when an arbitrary connected undirected graph, S (|S| ≤ 2) and T (|T| ≤ 2) are given. Moreover, our proposed algorithm can detect the non-existence of ST-reachable DAG if there exists no ST-reachable DAG of the given graph and two sets of vertices, S and T.