電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2015-04-23 14:10
頂点誘導部分グラフを列挙索引化するフロンティア法
鈴木浩史湊 真一北大
抄録 (和) 頂点誘導部分グラフとは,グラフ$G=(V,E)$の頂点部分集合$U subseteq V$を与えたとき,両端点が$U$に含まれる頂点である$E$の辺を辺集合とする部分グラフである.
本稿では,与えられたグラフ中で頂点誘導部分グラフとなりうる辺の組合せを列挙し,Zero-suppressed Binary Decision Diagram(ZDD)というデータ構造により索引化することを試みる.ZDDの構築には,ありうる辺の組合せを全て索引化したZDDを,一括してトップダウンに構築するフロンティア法と呼ばれる技法を用いる.我々は,与えられたグラフの任意の辺集合が頂点誘導部分グラフとなるための条件を明らかにし,それによりフロンティア法に基づく列挙索引化手法を実現した.計算実験の結果,本手法は日本の都道府県隣接関係を基にしたグラフ上で,22744781201224個もの頂点誘導部分グラフを,わずか0.01秒で列挙しZDDにより索引化した. 
(英) (Available after conference date)
キーワード (和) ZDD / フロンティア法 / 頂点誘導部分グラフ / 列挙問題 / / / /  
(英) ZDD / Frontier Method / Vertex Induced Subgraph / Enumeration Problem / / / /  
文献情報 信学技報, vol. 115, no. 15, COMP2015-3, pp. 15-20, 2015年4月.
資料番号 COMP2015-3 
発行日 2015-04-16 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 COMP  
開催期間 2015-04-23 - 2015-04-23 
開催地(和) 東北大学 
開催地(英)  
テーマ(和) (東北大学大学院情報科学研究科共催) 
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2015-04-COMP 
本文の言語 日本語 
タイトル(和) 頂点誘導部分グラフを列挙索引化するフロンティア法 
サブタイトル(和)  
タイトル(英) Frontier Method for Enumerating and Indexing the Vertex Induced Subgraphs 
サブタイトル(英)  
キーワード(1)(和/英) ZDD / ZDD  
キーワード(2)(和/英) フロンティア法 / Frontier Method  
キーワード(3)(和/英) 頂点誘導部分グラフ / Vertex Induced Subgraph  
キーワード(4)(和/英) 列挙問題 / Enumeration Problem  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 鈴木 浩史 / Hirofumi Suzuki / スズキ ヒロフミ
第1著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第2著者 氏名(和/英/ヨミ) 湊 真一 / Shin-ichi Minato / ミナト シンイチ
第2著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2015-04-23 14:10:00 
発表時間 30 
申込先研究会 COMP 
資料番号 IEICE-COMP2015-3 
巻番号(vol) IEICE-115 
号番号(no) no.15 
ページ範囲 pp.15-20 
ページ数 IEICE-6 
発行日 IEICE-COMP-2015-04-16 


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

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


IEICE / 電子情報通信学会