抄録
A-017
整数計画法によるグラフ焼失数の厳密計算
◎宮岡 誠（中大）・鮏川矩義（東理大）・浅野孝夫（中大）
ソーシャルグラフなどにおける影響伝播のしやすさを測る指標にグラフ焼失数がある.これは,隣接する頂点間で火が燃え移る(=影響が伝播する)と考え,グラフを焼き尽くすのに要する時間として定義される.パスなどの非常に特殊なグラフに対しては焼失数が簡単に計算できるが,一般には NP-完全であり,その挙動については不明な部分が多い.本研究では,一般のグラフに対して焼失数を厳密に計算する整数計画モデルを提案する.その有効性を数値実験によって検証し,さらに,計算時間の短縮法について議論する.
