A self-stabilizing algorithm for constructing a minimal reachable directed acyclic graph with two senders and two targets.

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 (i.e., a directed path exists) from every sender to every target. When an arbitrarily connected undirected graph G = (V , E) and two sets of the vertices, senders S (⊂ V) and targets T (⊂ V), are given, we consider the construction of a minimal ST -reachable DAG by changing some undirected edges to arcs and removing the remaining edges. In this paper, we present the necessary and sufficient condition under which a minimal ST -reachable DAG can be constructed when | S | ≤ 2 and | T | ≤ 2 , and propose a self-stabilizing algorithm for constructing a minimal ST -reachable DAG (if it exists) when an arbitrarily connected undirected graph, S (| S | ≤ 2) and T (| T | ≤ 2) are given. Moreover, our proposed algorithm can detect the non-existence of any ST -reachable DAG if the ST -reachable DAG of the given graph and two sets of vertices, S and T , do not exist. [ABSTRACT FROM AUTHOR]