IEICE TRANSACTIONS on Information
Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs
Summary :
Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n-3 or less.
- Publication
- IEICE TRANSACTIONS on Information Vol.E90-D No.4 pp.716-721
- Publication Date
- 2007/04/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e90-d.4.716
- Type of Manuscript
- PAPER
- Category
- Algorithm Theory
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
Keiichi KANEKO, "Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs" in IEICE TRANSACTIONS on Information,
vol. E90-D, no. 4, pp. 716-721, April 2007, doi: 10.1093/ietisy/e90-d.4.716.
Abstract: Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n-3 or less.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.4.716/_p
Copy
@ARTICLE{e90-d_4_716,
author={Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs},
year={2007},
volume={E90-D},
number={4},
pages={716-721},
abstract={Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n-3 or less.},
keywords={},
doi={10.1093/ietisy/e90-d.4.716},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 716
EP - 721
AU - Keiichi KANEKO
PY - 2007
DO - 10.1093/ietisy/e90-d.4.716
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2007
AB - Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n-3 or less.
ER -
English
