期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2018
卷号：8
期号：1
页码：53-72
语种：English
出版社：International Journal of Networking and Computing
摘要：We introduce a new network structure named a maximal (?, ?)-directed acyclic mixed graph (DAMG). A maximal (?, ?)-DAMG allows both arcs (directed edges) and (undirected) edges which is constructed, for any given connected undirected graph with a set of ? nodes specified as source nodes and a set of ? nodes specified as sink nodes, by assigning directions to as many (undirected) edges as possible (i.e., by changing edges into arcs) so that the following conditions are satisfied: (i) each node specified as a source node has at least one outgoing arc but no incoming arc, (ii) each node specified as a sink node has at least one incoming arc but no outgoing arc, (iii) each other node has no arc or has both outgoing and incoming arcs, and (iv) no directed cycle (consisting only of arcs) exists. This maximality implies that changing any more edges to arcs violates these conditions, for example, a source node has an incoming arc, a node which is specified as neither a source node nor a sink node has only outgoing or incoming arcs other than edges, or a directed cycle is created in the network. In this paper, we propose a self-stabilizing algorithm which constructs a (1,1)-maximal DAMG in any connected graph with a specified source node and a specified sink node by assigning directions to as many edges as possible.
其他摘要：We introduce a new network structure named a maximal (? , ? )-directed acyclic mixed graph (DAMG). A maximal (?, ? )-DAMG allows both arcs (directed edges) and (undirected) edges which is constructed, for any given connected undirected graph with a set of ? nodes specified as source nodes and a set of ? nodes specified as sink nodes, by assigning directions to as many (undirected) edges as possible (i.e., by changing edges into arcs) so that the following conditions are satisfied: (i) each node specified as a source node has at least one outgoing arc but no incoming arc, (ii) each node specified as a sink node has at least one incoming arc but no outgoing arc, (iii) each other node has no arc or has both outgoing and incoming arcs, and (iv) no directed cycle (consisting only of arcs) exists. This maximality implies that changing any more edges to arcs violates these conditions, for example, a source node has an incoming arc, a node which is specified as neither a source node nor a sink node has only outgoing or incoming arcs other than edges, or a directed cycle is created in the network. In this paper, we propose a self-stabilizing algorithm which constructs a (1,1)-maximal DAMG in any connected graph with a specified source node and a specified sink node by assigning directions to as many edges as possible.
关键词：Directed Acyclic Mixed Graph; Self-Stabilizing Algorithm; Maximal DAMG Construction
