d-clawfreeグラフの重み付き最大独立集合問題に対する近似アルゴリズムの実験的評価

摘要

d-clawとは，完全2部グラフK{sub}(1,d)と同型な誘導部分グラフである．d-clawを持たないグラフはd-clawfreeである．d-claw freeグラフの重み付き最大独立集合問題に対するいくつかの近似アルゴリズムが提案されている．本論文では，それらの近似アルゴリズムを実装し，実験的評価を行った．