グラフ上の相互排除のためのNDコータリ

概要

論文の詳細を見る
Coteries are used to solve the mutual exclusion problem. A coterie C on a graph G is said to G-dominate a coterie D on G if the following condition holds: For any minimal connected subgraph h of G containing a quorum in D, there exists a minimal connected subgraph h' of G containing a quorum in C such that h' is a subgraph of h. A coterie C on a graph G is said to be G-nondominated (G-ND) if no coterie D(=⃥C) on G G-dominates C. Very roughly speaking. a G-ND coterie has a good property that its availability is maximal, and hence the optimal coterie on G must be G-ND. In this paper, we show a necessary and sufficient condition for a coterie on a graph to be G-ND. We also show that if a coterie is nondominated in the sense of, we can determine it by checking a set of trees called cut-trees.
社団法人電子情報通信学会の論文
1995-03-27