特許ウォッチ

公開番号2024162516
公報種別公開特許公報(A)
公開日2024-11-21
出願番号2023078081
出願日2023-05-10
発明の名称部分グラフ数え上げ方法、部分グラフ数え上げ装置及びプログラム
出願人日本電信電話株式会社
代理人弁理士法人ITOH,個人,個人,個人
主分類G06F 17/10 20060101AFI20241114BHJP(計算;計数)
要約【課題】各頂点に対する部分グラフ数え上げ問題を高速に解く方法、装置及びプログラムを提供する。
【解決手段】方法は、連結な無向グラフと、ワイルドカードを含む連結性制約と、各辺の重みと、基礎となる部分グラフ集合とを入力する入力手順と、前記無向グラフの特定の頂点の集合の間の連結性に関する情報を持つノードで構成されるゼロサプレス型二分決定グラフZDDを構築する手順と、構築されたゼロサプレス型二分決定グラフと、前記各辺の重みとに基づいて、前記特定の頂点の集合の間の連結性に関する情報を利用した動的計画法により、各頂点に対して、前記部分グラフ集合に含まれる部分グラフであって、かつ、前記連結性制約に含まれるワイルドカードを頂点に置き換えた連結性制約を満たす部分グラフに含まれる辺の重みと前記部分グラフに含まれない辺の重みとを用いた重み付きカウント値を計算する計算手順と、を実行する。
【選択図】図8
特許請求の範囲【請求項１】
連結な無向グラフＧ＝（Ｖ，Ｅ）と、ワイルドカード＊を含む連結性制約Ｐ
＊
と、各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒと、基礎となる部分グラフ集合Ｆ⊆２
Ｅ
とを入力する入力手順と、
前記無向グラフＧと、前記連結性制約Ｐ
＊
と、前記部分グラフ集合Ｆ⊆２
Ｅ
とに基づいて、前記無向グラフＧの特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を持つノードで構成されるゼロサプレス型二分決定グラフＺを構築する構築手順と、
前記構築手順で構築されたゼロサプレス型二分決定グラフＺと、前記各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒとに基づいて、前記特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を利用した動的計画法により、各頂点ｖ∈Ｖに対して、前記部分グラフ集合Ｆに含まれる部分グラフＥ'であって、かつ、前記連結性制約Ｐ
＊
に含まれるワイルドカード＊を頂点ｖに置き換えた連結性制約Ｐ
＊
［ｖ］を満たす部分グラフＥ'に含まれる辺ｅ∈Ｅ'の重みｗ
ｅ
＋
と前記部分グラフＥ'に含まれない辺ｅ∈Ｅ＼Ｅ'の重みｗ
ｅ
－
を用いた重み付きカウント値ｃｏｕｎｔ（ｖ）を計算する計算手順と、
をコンピュータが実行する部分グラフ数え上げ方法。
続きを表示（約 1,900 文字）【請求項２】
前記部分グラフ集合Ｆ⊆２
Ｅ
は、前記無向グラフＧの部分グラフのうち、前記連結性制約Ｐ
＊
以外の所定の制約を満たす部分グラフの集合である、請求項１に記載の部分グラフ数え上げ方法。
【請求項３】
前記構築手順は、
前記部分グラフ集合ＦがＦ＝２
Ｅ
である場合、前記ワイルドカード＊も前記無向グラフＧの頂点の１つと扱ったフロンティア法により、前記部分グラフ集合Ｆ＝２
Ｅ
を表現する前記ゼロサプレス型二分決定グラフＺを構築する、請求項１に記載の部分グラフ数え上げ方法。
【請求項４】
前記構築手順は、
前記部分グラフ集合ＦがＦ≠２
Ｅ
である場合、前記ワイルドカード＊も前記無向グラフＧの頂点の１つと扱ったフロンティア法により、部分グラフ集合２
Ｅ
を表現するゼロサプレス型二分決定グラフＺ
１
を構築し、
フロンティア法により、前記部分グラフ集合Ｆを表現するゼロサプレス型二分決定グラフＺ
２
を構築し、
前記ゼロサプレス型二分決定グラフＺ
１
と前記ゼロサプレス型二分決定グラフＺ
２
との共通部分を前記ゼロサプレス型二分決定グラフＺとして構築する、請求項２に記載の部分グラフ数え上げ方法。
【請求項５】
連結な無向グラフＧ＝（Ｖ，Ｅ）と、ワイルドカード＊を含む連結性制約Ｐ
＊
と、各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒと、基礎となる部分グラフ集合Ｆ⊆２
Ｅ
とを入力する入力部と、
前記無向グラフＧと、前記連結性制約Ｐ
＊
と、前記部分グラフ集合Ｆ⊆２
Ｅ
とに基づいて、前記無向グラフＧの特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を持つノードで構成されるゼロサプレス型二分決定グラフＺを構築する構築部と、
前記構築部によって構築されたゼロサプレス型二分決定グラフＺと、前記各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒとに基づいて、前記特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を利用した動的計画法により、各頂点ｖ∈Ｖに対して、前記部分グラフ集合Ｆに含まれる部分グラフＥ'であって、かつ、前記連結性制約Ｐ
＊
に含まれるワイルドカード＊を頂点ｖに置き換えた連結性制約Ｐ
＊
［ｖ］を満たす部分グラフＥ'に含まれる辺ｅ∈Ｅ'の重みｗ
ｅ
＋
と前記部分グラフＥ'に含まれない辺ｅ∈Ｅ＼Ｅ'の重みｗ
ｅ
－
を用いた重み付きカウント値ｃｏｕｎｔ（ｖ）を計算する計算部と、
を有する部分グラフ数え上げ装置。
【請求項６】
連結な無向グラフＧ＝（Ｖ，Ｅ）と、ワイルドカード＊を含む連結性制約Ｐ
＊
と、各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒと、基礎となる部分グラフ集合Ｆ⊆２
Ｅ
とを入力する入力手順と、
前記無向グラフＧと、前記連結性制約Ｐ
＊
と、前記部分グラフ集合Ｆ⊆２
Ｅ
とに基づいて、前記無向グラフＧの特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を持つノードで構成されるゼロサプレス型二分決定グラフＺを構築する構築手順と、
前記構築手順で構築されたゼロサプレス型二分決定グラフＺと、前記各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒとに基づいて、前記特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を利用した動的計画法により、各頂点ｖ∈Ｖに対して、前記部分グラフ集合Ｆに含まれる部分グラフＥ'であって、かつ、前記連結性制約Ｐ
＊
に含まれるワイルドカード＊を頂点ｖに置き換えた連結性制約Ｐ
＊
［ｖ］を満たす部分グラフＥ'に含まれる辺ｅ∈Ｅ'の重みｗ
ｅ
＋
と前記部分グラフＥ'に含まれない辺ｅ∈Ｅ＼Ｅ'の重みｗ
ｅ
－
を用いた重み付きカウント値ｃｏｕｎｔ（ｖ）を計算する計算手順と、
をコンピュータに実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、部分グラフ数え上げ方法、部分グラフ数え上げ装置及びプログラムに関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
グラフ理論に属する問題の１つとして、部分グラフ数え上げ問題と呼ばれる問題が知られている。部分グラフ数え上げ問題とは、グラフが与えられたときに、或る所定の制約を満たす部分グラフの個数又は重み付きのカウント値を計算するという問題である。
【０００３】
部分グラフ数え上げ問題は、例えば、ネットワーク信頼性評価等に応用できる基本的な問題である。ネットワーク信頼性評価は或る２つの頂点間の連結性制約の下で部分グラフ数え上げ問題を解くことと同等であり、例えば、二分決定グラフ（ＢＤＤ：Binary Decision Diagram）を利用した高速な解法が知られている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００４】
Gary Hardy, Corinne Lucet, and Nikolaos Limnios. K-terminal network reliability measures with binary decision diagrams. IEEE Transactions on Reliability, Vol. 56, pp. 506-515, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、各頂点に対する部分グラフ数え上げ問題を解く場合、計算時間的に解くことが困難なことがあった。例えば、各頂点に対するネットワーク信頼性を評価する場合、頂点の個数だけ部分グラフ数え上げ問題を繰り返し解く必要があり、グラフの規模によっては非特許文献１に記載されている解法を利用しても現実的な計算時間で解くことが困難なことがある。
【０００６】
本開示は、上記の点に鑑みてなされたもので、各頂点に対する部分グラフ数え上げ問題を高速に解くことができる技術を提供する。
【課題を解決するための手段】
【０００７】
本開示の一態様による部分グラフ数え上げ方法は、連結な無向グラフＧ＝（Ｖ，Ｅ）と、ワイルドカード＊を含む連結性制約Ｐ
＊
と、各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒと、基礎となる部分グラフ集合Ｆ⊆２
Ｅ
とを入力する入力手順と、前記無向グラフＧと、前記連結性制約Ｐ
＊
と、前記部分グラフ集合Ｆ⊆２
Ｅ
とに基づいて、前記無向グラフＧの特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を持つノードで構成されるゼロサプレス型二分決定グラフＺを構築する構築手順と、前記構築手順で構築されたゼロサプレス型二分決定グラフＺと、前記各辺ｅ∈Ｅの重みｗ
ｅ
＋
，ｗ
ｅ
－
∈Ｒとに基づいて、前記特定の頂点ｖ∈Ｖの集合の間の連結性に関する情報を利用した動的計画法により、各頂点ｖ∈Ｖに対して、前記部分グラフ集合Ｆに含まれる部分グラフＥ'であって、かつ、前記連結性制約Ｐ
＊
に含まれるワイルドカード＊を頂点ｖに置き換えた連結性制約Ｐ
＊
［ｖ］を満たす部分グラフＥ'に含まれる辺ｅ∈Ｅ'の重みｗ
ｅ
＋
と前記部分グラフＥ'に含まれない辺ｅ∈Ｅ＼Ｅ'の重みｗ
ｅ
－
を用いた重み付きカウント値ｃｏｕｎｔ（ｖ）を計算する計算手順と、をコンピュータが実行する。
【発明の効果】
【０００８】
各頂点に対する部分グラフ数え上げ問題を高速に解くことができる技術が提供される。
【図面の簡単な説明】
【０００９】
ＺＤＤの一例を示す図である。
グラフの一例を示す図である。
二分決定木の一例を示す図である。
フロンティア法のアルゴリズムの一例を示す図である。
フロンティア法の結果として得られたＺＤＤの一例を示す図である。
本実施形態に係る部分グラフ数え上げ装置のハードウェア構成の一例を示す図である。
本実施形態に係る部分グラフ数え上げ装置の機能構成の一例を示す図である。
本実施形態に係る部分グラフ数え上げ処理の流れの一例を示すフローチャートである。
本実施形態に係る構築部が実行する処理のアルゴリズムの一例を示す図である。
本実施形態に係る計算部が実行する処理のアルゴリズムの一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の一実施形態について説明する。
（【００１１】以降は省略されています）

関連特許