4H-02
極大独立集合問題における並列性と解の精度
○根本　望，野村直也，藤井昭宏，田中輝雄（工学院大）
グラフ構造において、互いに枝で結ばれていない頂点の集合を独立集合と呼び、独立集合がなるべく大きくなるような頂点の組み合わせを求める問題を極大独立集合問題と呼ぶ.
この問題を解くために、主に2つの手法が提案されている.

1つ目は、各頂点に乱数値を与え、自身の値が隣接している全ての頂点の値よりも大きければその頂点を独立点として選んでいくという手法である.
この手法は、並列性は高いが選ばれる独立点は少なくなる.
2つ目は、一度独立点に決定した頂点を中心にその周囲に逐次的に独立点を決める手法である.
こちらの手法の場合、1つ目の手法とは反対に、独立点は多くなるが並列性は低い.

これらを踏まえた上で、2つの手法の長所を両立できるような新しい手法を考察する.
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会