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

講演抄録/キーワード
講演名 2019-09-02 16:00
二分決定図を用いた部分弦グラフと部分区間グラフの列挙
川原 純奈良先端大)・斎藤寿樹九工大)・鈴木浩史北大)・吉仲 亮東北大COMP2019-16
抄録 (和) 本論文では,与えられたグラフに対して,すべての部分弦グラフと
部分区間グラフの集合をそれぞれ表現する,ゼロサプレス型二分決定図と
呼ばれるデータ構造を構築するアルゴリズムを提案する.
提案アルゴリズムは,指定された性質を持つ部分グラフの集合を
表すゼロサプレス型二分決定図を構築する,既存の枠組みである
フロンティア法を拡張したものである.
計算機実験により,解を1つずつ出力する逆探索法に基づく既存アルゴリズムと,
提案アルゴリズムの比較を行う.本研究は国際会議
Special Event on Analysis of Experimental Algorithms (SEA^2 2019)
で発表された研究である. 
(英) This research proposes algorithms that construct compressed data
structures, called zero-suppressed binary decision diagrams,
which represent the sets of all the chordal and interval subgraphs
of a given graph, respectively.
The proposed algorithms are extensions of an existing framework,
called frontier-based search, to construct zero-suppressed
binary decision diagrams for the set of subgraphs satisfying specified conditions.
By numerical experiments, the proposed algorithms are compared
with existing reverse search-based algorithms, which output solutions one by one.
This research has been published at
Special Event on Analysis of Experimental Algorithms (SEA^2 2019).
キーワード (和) グラフアルゴリズム / グラフ列挙 / 二分決定図 / フロンティア法 / 区間グラフ / 弦グラフ / /  
(英) Graph algorithm / Graph enumeration / Decision diagram / Frontier-based search / Interval graph / Chordal graph / /  
文献情報 信学技報, vol. 119, no. 191, COMP2019-16, pp. 33-33, 2019年9月.
資料番号 COMP2019-16 
発行日 2019-08-26 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2019-16

研究会情報
研究会 COMP  
開催期間 2019-09-02 - 2019-09-02 
開催地(和) 岡山大学 津島キャンパス 
開催地(英) Tsushima Campus, Okayama University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2019-09-COMP 
本文の言語 日本語 
タイトル(和) 二分決定図を用いた部分弦グラフと部分区間グラフの列挙 
サブタイトル(和)  
タイトル(英) Enumeration of Chordal and Interval Subgraphs Using Binary Decision Diagrams 
サブタイトル(英)  
キーワード(1)(和/英) グラフアルゴリズム / Graph algorithm  
キーワード(2)(和/英) グラフ列挙 / Graph enumeration  
キーワード(3)(和/英) 二分決定図 / Decision diagram  
キーワード(4)(和/英) フロンティア法 / Frontier-based search  
キーワード(5)(和/英) 区間グラフ / Interval graph  
キーワード(6)(和/英) 弦グラフ / Chordal graph  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 川原 純 / Jun Kawahara / カワハラ ジュン
第1著者 所属(和/英) 奈良先端科学技術大学院大学 (略称: 奈良先端大)
Nara Institute of Science and Technology (略称: NAIST)
第2著者 氏名(和/英/ヨミ) 斎藤 寿樹 / Toshiki Saitoh / サイトウ トシキ
第2著者 所属(和/英) 九州工業大学 (略称: 九工大)
Kyushu Institute of Technology (略称: Kyutech)
第3著者 氏名(和/英/ヨミ) 鈴木 浩史 / Hirofumi Suzuki / スズキ ヒロフミ
第3著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第4著者 氏名(和/英/ヨミ) 吉仲 亮 / Ryo Yoshinaka / ヨシナカ リョウ
第4著者 所属(和/英) 東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.)
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-09-02 16:00:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2019-16 
巻番号(vol) IEICE-119 
号番号(no) no.191 
ページ範囲 p.33 
ページ数 IEICE-1 
発行日 IEICE-COMP-2019-08-26 


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

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


IEICE / 電子情報通信学会