@misc{oai:uec.repo.nii.ac.jp:00008474,
 author = {高木, 雄大},
 month = {2017-03-13},
 note = {2016, 本研究では最長路問題について扱う。最長路問題とは、入力グラフに対する部分グラフの中で辺数が最大のオイラーグラフまたは準オイラーグラフを求める問題である。
　ランダムグラフ上の最長路問題は高い辺密度においては高確率で最大流問題から最長路が誘導されることが示唆されている。しかし、辺密度の低いグラフにおいてはその確率が大きく減少していることも観察されている。そこで、本研究では最長路問題の計算複雑性がNP 困難であることを示し、その問題に対する最大流問題と強連結成分分解を用いた発見的アルゴリズムを提案する。提案アルゴリズムは、まず入力グラフの強連結成分分解を求める。次にそれによって得られた分割の順序関係の順に各強連結成分における最大流問題を解く。このとき、2 番目以降の強連結成分について考える場合、それより前の強連結成分における流れも用いることができる場合が存在することに注意して最大流問題を解く。例えば、2 番目の強連結成分の中に1 番目の強連結成分のみを通って辿り着ける頂点が存在する場合、その流れが使えることを踏まえた上で最大流問題を解く。そして、最終的に得られた最大の流れを解として出力する。ただし、提案アルゴリズムは必ずしも最長路問題の最適解を出力するものではない。そこで本論文では、提案アルゴリズムが多項式時間で動作することを証明した後、最長路が得られる確率を実験により求めた。
　実験では、頂点数が10, 20 の場合については辺密度を0.01 から0.50 まで0.01 刻みで、頂点数30, 40, 50 の場合については辺密度を0.005 から0.25 まで0.005 刻みで、それぞれ1000 個のランダムグラフをデータとして用意し、最大流問題を一度だけ解いて最長路が得られるデータの割合と提案アルゴリズムを適用した場合に最長路が得られるデータの割合をそれぞれ調べた。実験の結果、最大流問題を一度だけ解いた場合に最長路が得られた割合で最も低かった値はそれぞれ、頂点数が10 のときは0.484%、20 のときは0.382%、30 のときは0.271%、40 のときは0.242%、50 のときは0.218%という結果が得られた。それに対し、提案アルゴリズムを適用した場合に最長路が得られたデータの割合で最も低かったときの値はそれぞれ、頂点数が10のときは0.987%、20 のときは0.973%、30 のときは0.958%、40 のときは0.956%、50 のときは0.938%という結果が得られた。これにより、提案アルゴリズムを適用する場合は最大流問題を一度だけ解く場合に対し、最長路が得られる確率が大きく改善することがわかった。
　以上より、本研究の提案アルゴリズムはNP 困難な最長路問題をランダムグラフ上においては多項式時間で高確率に解けるアルゴリズムであることが示唆された。},
 title = {ランダムグラフ上の最長路問題に対する発見的アルゴリズム},
 year = {},
 yomi = {タカギ, ユウダイ}
}