http://swrc.ontoware.org/ontology#TechnicalReport
Reconfiguration of Linear Extensions
en
Iwate University
Iwate University
Iwate University
Hokkaido University
Taishu Ito
Katsuhisa Yamanaka
Takashi Hirayama
Yasuaki Kobayashi
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.
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-191
1
1-7
2023-01-12
2188-8566