2B-2
木ネットワークにおける証明書分散問題の近似可能性について
○泉 泰介（名工大），泉 朋子（立命館大），小野廣隆（九大），和田幸一（名工大）
証明書分散問題は，与えられた通信要求をセキュアに実現するために
各計算機が保有しなければいけない証明書の枚数を最小化する組み合わせ
最適化問題である．本研究では，通信要求グラフ，および証明書グラフが
木の場合における証明書分散問題の計算困難性について論じる．通信要求
グラフが木の場合，その最大次数によって計算困難さが変化すること，
および証明書グラフが木の場合は多項式時間で最適解を求めることが
可能であることを示す．