最小全域木の文献(調査候補2/5)

Expected Runtimes of a Simple Evolutionary Algorithm for the Multi-objective Minimum Spanning Tree problem

多目的最小全域木問題というのが何かは良く分からないけど、MOCKで扱うMSTは単一目的な気がする。多目的だと数理的に解くのが難しくなるのだろうか?ちなみに単一目的のMST生成はO(N*logN)。ま、とりあえずアブストだけ。

Abstract

進化的計算は組み合わせ最適化問題のように、数理的に厳密に解決できない問題に適用される。こういった探索ヒューリスティクス解析法はある種の有名な可解多項式への適用に端を発する。現在ではこれらの解析法は異なる問題でも進化的アルゴリズムの方向に向かっている。本論ではNP困難多目的最小全域木問題を扱い、単純な進化的アルゴリズムがパレート最適化フロントの全ての極値点に対応する全域木を求めるのに必要な実行時間の上限値を求める。