The search functionality is under construction.

Author Search Result

[Author] Yuuki AOIKE(1hit)

1-1hit
  • Finding a Reconfiguration Sequence between Longest Increasing Subsequences Open Access

    Yuuki AOIKE  Masashi KIYOMI  Yasuaki KOBAYASHI  Yota OTACHI  

     
    LETTER-Fundamentals of Information Systems

      Pubricized:
    2023/12/11
      Vol:
    E107-D No:4
      Page(s):
    559-563

    In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely LONGEST INCREASING SUBSEQUENCE RECONFIGURATION. We give a polynomial-time algorithm for deciding whether there is a reconfiguration sequence between two longest increasing subsequences in a sequence. This implies that INDEPENDENT SET RECONFIGURATION and TOKEN SLIDING are polynomial-time solvable on permutation graphs, provided that the input two independent sets are largest among all independent sets in the input graph. We also consider a special case, where the underlying permutation graph of an input sequence is bipartite. In this case, we give a polynomial-time algorithm for finding a shortest reconfiguration sequence (if it exists).