A self-stabilizing algorithm for constructing amaximal (ğœ, ğœ)-directed acyclic mixed graph

摘要

A (sigma,tau)-directed acyclic mixed graph (DAMG) is a mixed graph, which allows both arcs (or directed edges) and (undirected) edges such that there exist exactly sigma source nodes and tau sink nodes, but there exists no directed cycle (consisting of only arcs). Each source (resp. sink) node has at least one outgoing (resp. incoming) arc, but no incoming (resp. outgoing) arc. Moreover any other node is neither a source nor a sink node; it has no incident arc or both outgoing and incoming arcs. This article considers maximal (sigma,tau)-DAMG constructions: when an arbitrary undirected connected graph G=(V,E) and two distinct subsets S and T of node set V, where |S|=sigma and |T|=tau, are given, construct a maximal (sigma,tau)-DAMG with source node set S and sink node set T by assigning directions to as many edges as possible (ie, by changing edges into arcs). The maximality implies that changing any more edges to arcs violates the conditions of a (sigma,tau)-DAMG (eg, a sink node has an outgoing arc or a directed cycle is created). As a previous work, a self-stabilizing algorithm for constructing a maximal (1,1)-DAMG in an arbitrary undirected connected graph is proposed for the case of sigma=tau=1. In this article, we consider construction of a maximal (sigma,tau)-DAMG for any sigma and tau. First, we introduce a self-stabilizing algorithm for a maximal (1,2)-DAMG construction in any connected graph (with few constraints), which is based on the previous work. Concerning generalization of sigma and tau to arbitrary values, we first clarify the necessary and sufficient condition under which a (sigma,tau)-DAMG can be constructed in which a source and a sink node sets are given. Then, we propose a generalized self-stabilizing algorithm that constructs a (sigma,tau)-DAMG when a given graph with a source and a sink node sets satisfies the above condition.