Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs

Sinyu JUNG; Keiichi KANEKO

doi:10.1587/transinf.2022EDP7211

Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs

Sinyu JUNG, Keiichi KANEKO

Full Text Views

0

Cite this

Summary :

A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2^n-1(n-1)!(n-3.5).

Publication: IEICE TRANSACTIONS on Information Vol.E106-D No.10 pp.1677-1685

Publication Date: 2023/10/01

Publicized: 2023/06/30

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2022EDP7211

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Authors

Sinyu JUNG
Tokyo University of Agriculture and Technology
Keiichi KANEKO
Tokyo University of Agriculture and Technology

Keyword

dependability, graph theory, livelock, parallel computation

Cite this

Copy

Sinyu JUNG, Keiichi KANEKO, "Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs" in IEICE TRANSACTIONS on Information, vol. E106-D, no. 10, pp. 1677-1685, October 2023, doi: 10.1587/transinf.2022EDP7211.
Abstract: A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2^n-1(n-1)!(n-3.5).
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7211/_p

Copy

@ARTICLE{e106-d_10_1677,
author={Sinyu JUNG, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs},
year={2023},
volume={E106-D},
number={10},
pages={1677-1685},
abstract={A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2^n-1(n-1)!(n-3.5).},
keywords={},
doi={10.1587/transinf.2022EDP7211},
ISSN={1745-1361},
month={October},}

Copy

TY - JOUR
TI - Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1677
EP - 1685
AU - Sinyu JUNG
AU - Keiichi KANEKO
PY - 2023
DO - 10.1587/transinf.2022EDP7211
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2023
AB - A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2^n-1(n-1)!(n-3.5).
ER -