A (alpha,tau)-directed acydic mixed graph (DAMG) is a mixed graph which allows both arcs (or directed edges) and (undirected) edges such that there exists exactly a source nodes and tau sink nodes but there exists no ...
详细信息
ISBN:
(纸本)9781538691823
A (alpha,tau)-directed acydic mixed graph (DAMG) is a mixed graph which allows both arcs (or directed edges) and (undirected) edges such that there exists exactly a 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 arc or both outgoing and incoming arcs. This paper considers maximal (sigma, tau)-DAMG construction: when an arbitrary undirected connected graph G = (V, E) and two distinct subsets S and T of node set V, where vertical bar S vertical bar=sigma and vertical bar T vertical bar=tau. are given. construct a maximal (sigma, T)-DAMG with source node set S and sink node set T by assigning directions to as many edges as possible (i.e, by changing edges into arcs). The maximality implies that changing any more edges to arcs violates the conditions of a (sigma, T)-DAMG (e.g., a sink node has an outgoing arc or a directed cyde is created). In this paper, at first, we propose a self-stabilizingalgorithm for the maximal (1,2)-DAMG construction in any connected graph (with few constraints). Finally, we propose a self-stabilizingalgorithm for the maximal (2,2)-DAMG construction problem, which is an extension of the algorithm for constructing a maximal (1,2)-DAMG.
We propose a simple and elegant distributed self-stabilizingalgorithm to find the center of an arbitrary tree graph. The algorithm is uniform over all nodes of the tree. We prove the self-stabilization of the distrib...
详细信息
We propose a simple and elegant distributed self-stabilizingalgorithm to find the center of an arbitrary tree graph. The algorithm is uniform over all nodes of the tree. We prove the self-stabilization of the distributed algorithm using mathematical induction; we did not need to design a bounded function on the global state (which is customary for proving correctness of self-stabilizingalgorithms).
暂无评论