Minimum Feedback Node Sets in Trivalent Cayley Graphs

Yasuto SUZUKI  Keiichi KANEKO  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.9   pp.1634-1636
Publication Date: 2003/09/01
Online ISSN: 
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>>
Buy this Article

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.