A self‐stabilizing algorithm for constructing a maximal (σ, τ)‐directed acyclic mixed graph. (5th May 2020)

• Record Type: Journal Article
• Authors: Kim, Yonghwan; Katayama, Yoshiaki; Masuzawa, Toshimitsu
• Is Part Of: Concurrency and computation. Volume 33:Number 12(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-05-05
• Subjects: directed acyclic mixed graph -- graph constructions -- self‐stabilization; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5812
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: A ( σ, τ )‐directed acyclic mixed graph (DAMG) is a mixed graph, which allows both arcs (or directed edges) and (undirected) edges such that there exist exactly σ source nodes and τ 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 ( σ, τ )‐DAMG constructions: when an arbitrary undirected connected graph G =( V, E ) and two distinct subsets S and T of node set V, where | S |= σ and | T |= τ, are given, construct a maximal ( σ, τ )‐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 ( σ, τ )‐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 σ = τ =1. In this article, we consider construction of a maximal ( σ, τ )‐DAMG for any σ and τ . 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 σ and τ to arbitrary values, we first clarify the necessary and sufficient condition under which a ( σ, τ )‐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 ( σ, τ )‐DAMG when a given graph with a source and a sink node sets satisfies the above condition.