誘導部分グラフ検出のための分散計算
Distributed subgraph detection for induced subgraphs

概要

分散計算の分野では、ある無向グラフの頂点が計算機を表し、辺が直接通信可能な計算機同士を結んでいると考え、各計算機が計算と通信を同期的に繰り返してある問題を解く計算モデルを扱う。この計算機のネットワークが特定のグラフを部分グラフとして含むかどうかを判定する問題を分散計算の枠組みで解くことは近年盛んに研究されている。本研究では、誘導部分グラフ判定問題を分散計算のモデルで解くことを想定して、理論的な限界を解析している。また、計算機を量子計算機とし量子ビットを通信するモデルである量子分散計算が持つ、通常の分散計算に対する(誘導部分グラフ検出問題における)優位性についても紹介する。

産業界への展開例・適用分野

計算機一台では処理できないような巨大な問題を扱いたい場合や個々の計算機の処理能力が低い場合に問題を解くための手段として分散計算が利用できる。
また、「誘導部分グラフ判定問題」は、グラフ理論の分野における基礎的な問題の一つで、インターネットやSNSの解析など様々な応用がある。さらに量子分散計算は将来、量子計算機が実用化された場合に、その優位性を評価することにつながる。

研究者

氏名	専攻	研究室	役職/学年
宮本 昌幸	通信情報システム専攻	湊研究室	修士1回生
Le Gall François	その他所属	名古屋大学大学院多元数理科学研究科	准教授
湊 真一	通信情報システム専攻	湊研究室	教授

---