お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2016-06-24 15:45
ゼロサプレス型二分決定グラフによる文字グラフの列挙
川原 純奈良先端大)・○斎藤寿樹神戸大)・吉仲 亮東北大COMP2016-8
抄録 (和) ゼロサプレス型二分決定グラフ(ZDD)は、集合族をコンパクトに表現するデータ構造である。グラフが 与えられたとき、ZDD を用いて、問題に応じた様々な条件を満たす部分グラフをすべて列挙する枠組みが提案されて おり、フロンティア法と呼ばれている。本稿では、フロンティア法を用いて、指定した次数の頂点を指定した個数も つ部分グラフをすべて列挙する手法を提案する。さらに、ZDD として与えられた 2 つの集合族から共通な要素をも たないように(またはもつように)それぞれ集合を取り出して和集合を求め、それらを集めることによって得られる 集合族を表す ZDD を求める手法を提案する。これらの手法を組合せて、文字グラフと呼ばれるグラフの列挙を行う。 計算機実験によって文字グラフの集合を表す ZDD が構築できることを確認する。 
(英) A zero-suppressed binary decision diagram (ZDD) is a compact data structure that represents a family of sets. A framework is proposed that enumerates subgraphs of a given graph satisfying various specified conditions. In this paper, an algorithm is proposed that enumerates subgraphs of a given graph which have a specific number of vertices of specific degrees. Some ZDD operations are also proposed to compute the family of sets which are the unions of disjoint/overlapping sets from two given families. Roman alphabet letter graphs on a given graph are enumerated by the combination of the methods. The performance of our algorithm is confirmed by numerical experiments.
キーワード (和) グラフアルゴリズム / BDD/ZDD / フロンティア法 / 列挙問題 / / / /  
(英) Graph algorithm / BDD/ZDD / frontier-based search / enumeration problem / / / /  
文献情報 信学技報, vol. 116, no. 116, COMP2016-8, pp. 33-40, 2016年6月.
資料番号 COMP2016-8 
発行日 2016-06-17 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2016-8

研究会情報
研究会 COMP IPSJ-AL  
開催期間 2016-06-24 - 2016-06-25 
開催地(和) 石川県教育会館 
開催地(英)  
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2016-06-COMP-AL 
本文の言語 日本語 
タイトル(和) ゼロサプレス型二分決定グラフによる文字グラフの列挙 
サブタイトル(和)  
タイトル(英) Enumerating Letter Graphs by Zero-suppressed Decision Diagrams 
サブタイトル(英)  
キーワード(1)(和/英) グラフアルゴリズム / Graph algorithm  
キーワード(2)(和/英) BDD/ZDD / BDD/ZDD  
キーワード(3)(和/英) フロンティア法 / frontier-based search  
キーワード(4)(和/英) 列挙問題 / enumeration problem  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 川原 純 / Jun Kawahara / カワハラ ジュン
第1著者 所属(和/英) 奈良先端科学技術大学院大学 (略称: 奈良先端大)
Nara Institute of Science and Tecnology (略称: NAIST)
第2著者 氏名(和/英/ヨミ) 斎藤 寿樹 / Toshiki Saitoh / サイトウ トシキ
第2著者 所属(和/英) 神戸大学 (略称: 神戸大)
Kobe University (略称: Kobe Univ.)
第3著者 氏名(和/英/ヨミ) 吉仲 亮 / Ryo Yoshinaka / ヨシナカ リョウ
第3著者 所属(和/英) 東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2016-06-24 15:45:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2016-8 
巻番号(vol) IEICE-116 
号番号(no) no.116 
ページ範囲 pp.33-40 
ページ数 IEICE-8 
発行日 IEICE-COMP-2016-06-17 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会