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

スポンサーリンク

概要

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

著者

関連論文

もっと見る

スポンサーリンク