重みつきコーダルグラフ上の重み最小極大独立点集合の探索問題

摘要

重みつきグラフ中の重み最小極大独立点集合探索問題は，グラフに関する問題の中で最も基本的な問題の一つである．一般のグラフに対して任意の重みつきを許すと，この問題はNP困難となることが知られている．更にこの問題はコーダルグラフ中に限定しても，重みを任意に許すとNP困難になることが知られている．しかし，0と1に限定した時には線形時間で解くことのできるアルゴリズムが存在する。 ただし，このアルゴリズムは線形計画法を用いて解くという点に大きな特徴がある．本研究では組合せ論的手法により0，1，2の重みつきコーダルグラフ中の重み最小極大独立点集合探索の多項式時間アルゴリズムを提案した．