2024-02-25T22:08:23Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002233642023-04-27T10:00:04Z01164:02592:11085:11086
Reconfiguration of Linear ExtensionsReconfiguration of Linear Extensionsenghttp://id.nii.ac.jp/1001/00223255/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=223364&item_no=1&attribute_id=1&file_no=1Copyright (c) 2023 by the Information Processing Society of JapanIwate UniversityIwate UniversityIwate UniversityHokkaido UniversityTaishu, ItoKatsuhisa, YamanakaTakashi, HirayamaYasuaki, KobayashiIn this paper, we investigate the problem of reconfiguring two linear extensions of a poset on X = {1, 2,..., n}. We are given two linear extensions L, L′ of a poset. The problem asks to find a shortest reconfiguration sequence between L and L′ under the designated reconfiguration rules. In this paper, we use adjacent transpositions and shifts as the rules. We first characterize the length of shortest reconfiguration sequence of two linear extensions and show an algorithm that computes a shortest reconfiguration sequence under adjacent transpositions. We also characterize the length of shortest reconfiguration sequence of two linear extensions and show an algorithm that computes a shortest reconfiguration sequence under shifts.In this paper, we investigate the problem of reconfiguring two linear extensions of a poset on X = {1, 2,..., n}. We are given two linear extensions L, L′ of a poset. The problem asks to find a shortest reconfiguration sequence between L and L′ under the designated reconfiguration rules. In this paper, we use adjacent transpositions and shifts as the rules. We first characterize the length of shortest reconfiguration sequence of two linear extensions and show an algorithm that computes a shortest reconfiguration sequence under adjacent transpositions. We also characterize the length of shortest reconfiguration sequence of two linear extensions and show an algorithm that computes a shortest reconfiguration sequence under shifts.AN1009593X研究報告アルゴリズム（AL）2023-AL-1911172023-01-122188-85662022-12-28