For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Minimum Feedback Node Sets in Trivalent Cayley Graphs
Yasuto SUZUKI Keiichi KANEKO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
feedback node set, trivalent Cayley graphs, interconnection networks,
Full Text: PDF>>
A minimum feedback node set in a 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.