Minimum Feedback Node Sets in Trivalent Cayley Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
スポンサーリンク
概要
- 論文の詳細を見る
A minimum feedback node set ina graph is a minimum node subset whose deletion makes the graph acyclic. Its detection in a dependency graph is important to recover from a deadlock configuration. A livelock configuration is also avoidable if a check point is set in each node in the minimum feedback node set. Hence, its detection is very important to establish dependable network systems. In this letter, we give a minimum feedback node set in a trivalent Cayley graph. Assuming that each word has n bits, for any node, we can judge if it is included in the set or not in constant time.
- 社団法人電子情報通信学会の論文
- 2003-09-01
著者
-
Kaneko Keiichi
Faculty Of Technology Tokyo University Of Agriculture And Technology
-
Suzuki Yasuto
Faculty Of Technology Tokyo University Of Agriculture And Technology
関連論文
- Internally-Disjoint Paths Problem in Bi-Rotator Graphs(Dependable Computing)
- Node-to-Set Disjoint Paths Problem in Pancake Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
- Node-Disjoint Paths Algorithm in a Transposition Graph(Algorithm Theory)
- An Algorithm for Node-Disjoint Paths in Pancake Graphs
- Minimum Feedback Node Sets in Trivalent Cayley Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
- Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks
- An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs(Dependable Communication)(Dependable Computing)