Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach
Summary :
In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.4 pp.842-848
- Publication Date
- 2002/04/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section of Selected Papers from the 14th Workshop on Circuits and Systems in Karuizawa)
- 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
Toru ARAKI, Yukio SHIBATA, "Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 4, pp. 842-848, April 2002, doi: .
Abstract: In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_4_842/_p
Copy
@ARTICLE{e85-a_4_842,
author={Toru ARAKI, Yukio SHIBATA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach},
year={2002},
volume={E85-A},
number={4},
pages={842-848},
abstract={In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 842
EP - 848
AU - Toru ARAKI
AU - Yukio SHIBATA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2002
AB - In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).
ER -
English
