Minimum Feedback Node Sets in Trivalent Cayley Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.9 pp.1634-1636
- Publication Date
- 2003/09/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section LETTER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yasuto SUZUKI, Keiichi KANEKO, "Minimum Feedback Node Sets in Trivalent Cayley Graphs" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 9, pp. 1634-1636, September 2003, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_9_1634/_p
Copy
@ARTICLE{e86-d_9_1634,
author={Yasuto SUZUKI, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Minimum Feedback Node Sets in Trivalent Cayley Graphs},
year={2003},
volume={E86-D},
number={9},
pages={1634-1636},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Minimum Feedback Node Sets in Trivalent Cayley Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1634
EP - 1636
AU - Yasuto SUZUKI
AU - Keiichi KANEKO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2003
AB - 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.
ER -
English
