迂回の特性を捉えた最短遷移アルゴリズムに関する研究

点击翻译按钮获取中文摘要

本年度は，遷移させる対象として（すなわち，解空間グラフの頂点として）入力グラフの部分木を考え，関連する遷移問題を解析した．無向グラフだけでなく，有向グラフも対象として研究を行った．同じサイズの部分木を遷移させる対象とした場合，無向グラフであれば解空間グラフは常に連結となる．しかしながら，有向グラフである場合には，この性質は成り立たない．有向グラフにおける部分木の定義は，ここでは省略するが，比較的単純なグラフでも，遷移ができない2つの有向部分木を見つけることができてしまう．このような従来研究とは性質が異なる解空間グラフについて，本研究では解析を進め，アルゴリズム開発を行った．また，遷移させる対象が，入力グラフの2点sとtを繋ぐ最短パスである場合も研究した．この遷移問題は，これまでもよく研究されており，入力グラフの構造に基づく計算複雑性の解析が広くなされてきた．これに対して，複数のstペアを導入し，それらが点素な最短パスで繋がれる場合の遷移問題を考えた．従来の単一のstペアの場合とは，計算複雑性の観点から異なる結果をいくつか与えることができている．特に，単一のstペアであれば最短遷移が多項式時間で解けていた場合であっても，複数のstペアでは計算困難になることが示せ，興味深い知見を得ることができた．本研究では他にも，完全マッチングの最短遷移に関する論文を学術雑誌にて発表したり，有向グラフにおける独立集合の遷移問題を研究したりした．