2024-03-29T15:02:33Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001876072023-11-17T02:17:36Z06504:09465:09472
グラフ列挙における構築途中のZDD幅に基づく変数順序づけ法jpnソフトウェア科学・工学http://id.nii.ac.jp/1001/00187519/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=187607&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of Japan北大北大鈴木, 浩史湊, 真一ZDDは組合せ集合を効率よく圧縮して索引化するデータ構造である.グラフといくつかのトポロジー制約が与えられたとき,それを満たす部分グラフを全列挙するZDDを高速に構築する「フロンティア法」という技法が最近注目されている.フロンティア法の課題として,生成するZDDサイズが変数順序に大きく左右されることが挙げられる.従来のフロンティア法では,前処理で変数順序を固定するヒューリスティックな順序付けが用いられてきた.しかし,ZDDサイズは構築が進むまで不明であり,必ずしも最適に近い順序が得られるわけではない.そこで本研究では,構築途中のZDD幅を考慮しつつ,並行して良い変数順序を求める手法を提案する.AN00349328第80回全国大会講演論文集201811591602018-03-132018-05-01