特許

J-GLOBAL ID：201803004191204264

ZSDD構築装置、方法、及びプログラム

発明者： 西野 正彬 ,  安田 宜仁 ,  湊 真一
出願人/特許権者： 日本電信電話株式会社 ,  国立大学法人北海道大学
代理人 (1件)： 特許業務法人太陽国際特許事務所
公報種別：公開公報
出願番号（国際出願番号）：特願2016-173031
公開番号（公開出願番号）：特開2018-041161
出願日： 2016年09月05日
公開日（公表日）： 2018年03月15日
要約：

【課題】集合族間の各種演算を高速に行うためのZSDD(Zero-suppressed Sentential Decision Diagram)を効率的に構築する。【解決手段】ZSDD構築装置100の演算部20において、ZSDD構築部32が、グラフのエッジ集合に含まれる各要素に対応するノードを葉ノードとして表現したvtreeのノードに対応する決定ノードと、集合を部分集合X、Yへ分割したときの、集合に含まれる要素又は定数である記号を表す終端ZSDD又は決定ノードへの矢印を表す決定ZSDDであるプライムとサブとのペアを表す要素ノードとを含むZSDDを構築し、vtreeの各ノードを、根ノードから順番に対象ノードとし、vtreeの対象ノードを参照して、再帰的にZSDDを構築する。【選択図】図4

請求項（抜粋）：

入力されたグラフに基づいて、ノードとエッジとからなる完全二分木であって、前記グラフのエッジ集合Eに含まれる各要素に対応するノードを葉ノードとして表現したvtreeを構築するvtree構築部と、 前記グラフと、前記構築されたvtreeと、に基づいて、前記グラフのマッチングを表す前記エッジ集合Eの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記vtreeのノードに対応する決定ノードと、前記エッジ集合Eを部分集合X、Yへ分割したときの、前記エッジ集合Eに含まれる要素又は定数である記号を表す終端ZSDD又は前記決定ノードへの矢印を表す決定ZSDDであるプライムとサブとのペアを表す要素ノードとを含むZSDD(Zero-suppressed Sentential Decision Diagram)を構築するZSDD構築部と、 を含み、 前記ZSDD構築部は、前記構築されたvtreeの各ノードを、根ノードから順番に対象ノードとし、前記vtreeの対象ノードを参照して、再帰的にZSDDを構築するZSDD構築装置。

IPC (1件)：

G06F 17/10

FI (1件)：

G06F17/10 Z

Fターム (1件)：

5B056BB00