Chordal SupergraphとChordal Subgraphによる最大クリーク問題の緩和問題構成法について

摘要

ラグランジュ緩和法は，いくつかの組合せ最適化問題に射し非常に良い上界を与えることが知られている．しかし，最大クリーク問題にラグランジュ緩和法をそのまま適用してもよい上界は得られない．ラグランジュ緩和を用いて良い上界を得る手法として，筆者らは以前にchordal supergraphを用いる手法を提案したが，本稿ではその手法を改良したものを示す．また，新たにvertex induced chordal subgraphを用いる手法を提案する．そして，捷案法が良い上界を与えることを計算機実験により示す．