The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Sinyu JUNG(1hit)

1-1hit
  • Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs

    Sinyu JUNG  Keiichi KANEKO  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2023/06/30
      Vol:
    E106-D No:10
      Page(s):
    1677-1685

    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, 2n-1(n-1)!(n-3.5).