キャタピラグラフの独立点集合遷移問題に対する多項式時間アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2014-02-24
• タイトル: キャタピラグラフの独立点集合遷移問題に対する多項式時間アルゴリズム
• タイトル / 言語: en
• タイトル: Linear time algorithm for Independent Set Reconfiguration Problem on a caterpillar graph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学情報科学研究科
• 著者所属: 北陸先端科学技術大学院大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): School of Information Science, JAIST
• 著者所属(英): en
• 著者所属(英): School of Information Science, JAIST
• 著者名: 山田, 武; 上原, 隆平
• 著者名(英): Takeshi, Yamada; Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフ G に対し，|Ⅱb|=|Ⅱr| であるような 2 つの独立点集合 Ⅱb と Ⅱr が与えられたとする．また，G において，Ⅱb に含まれる各点にはトークンが置かれているとする．スライディングトークン問題とは，Ⅱb から Ⅱr への G の独立点集合の系列が存在するか判定する問題である．ただし，系列に含まれる各独立点集合は，その 1 つ前の独立点集合から，ただ 1 つのトークンを G の辺に沿ってスライドさせることで得られなければならない．本論文では，キャタピラグラフに対して，この問題が線形時間で解けることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Suppose that we are given two independent sets Ⅱb and Ⅱr of a graph such that |Ⅱb|=|Ⅱr|, and imagine that a token is placed on each vertex in Ⅱb. Then, SLIDING TOKEN is to determine whether there exists a sequence of independent sets which transforms Ⅱb into Ⅱr so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. In this paper, we show that the problem is solvable in linear time for caterpillar graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2014-AL-147, 号 11, p. 1-5, 発行日 2014-02-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会