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

Abstract 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.