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

• 山田 武

  北陸先端科学技術大学院大学情報科学研究科

• 上原 隆平

  北陸先端科学技術大学院大学情報科学研究科

書誌事項

タイトル別名

• Linear time algorithm for Independent Set Reconfiguration Problem on a caterpillar graph

抄録

グラフ G に対し,|?b|=|?r| であるような 2 つの独立点集合 ?b と ?r が与えられたとする.また,G において,?b に含まれる各点にはトークンが置かれているとする.スライディングトークン問題とは,?b から ?r への G の独立点集合の系列が存在するか判定する問題である.ただし,系列に含まれる各独立点集合は,その 1 つ前の独立点集合から,ただ 1 つのトークンを G の辺に沿ってスライドさせることで得られなければならない.本論文では,キャタピラグラフに対して,この問題が線形時間で解けることを示す.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2014 (11), 1-5, 2014-02-24

  一般社団法人情報処理学会

詳細情報

• CRID: 1573668927625959040
• NII論文ID: 110009675760
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles