CD-001
最大k-plex問題に対する効率的な枝刈りアルゴリズム

◎真次彰平・塩川浩昭（筑波大）

k-plexは，部分グラフ中のエッジの欠損数に基づく密部分グラフの定義である．グラフ中の最大のk-plexを求める最大k-plex問題は，ノード枝刈りを用いたグラフサイズの削減によるアプローチが有力である．しかしながら，最大k-plex問題を解く既存手法は同一のノード集合に対して線形時間を要する枝刈り処理を繰り返し実行するため低速である．そこで本稿では枝刈り探索をメモ化することにより枝刈り処理自体に要する実行時間を削減した高速な解法を提案する．実験により提案手法は同一のノードへの参照回数を大幅に削減し，複数のデータセットに対して既存手法と同等の計算結果を最大50倍高速に得られることを確認した．