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

講演抄録/キーワード
講演名 2017-12-22 14:40
k-縮退グラフ中の支配集合の効率良い列挙
栗田和宏北大)・和佐州洋宇野毅明NII)・有村博紀北大ISEC2017-89 COMP2017-43
抄録 (和) 支配集合はクリークや,独立点集合,s-t パス,カットのように基本的なグラフ構造の一つである.クリー ク等のグラフ構造には極大や極小の構造を多項式遅延時間で列挙するアルゴリズムが知られている.しかし,極小支 配集合を多項式遅延もしくはならし多項式時間で列挙するアルゴリズムが存在するかどうかはわかっていない.さら に,極小でない支配集合を含めた全ての支配集合の列挙についてはあまり研究が行われていない.本論文では極小な 支配集合だけでなく,全ての支配集合の列挙を行う.主結果として,我々は効率の良い支配集合の列挙アルゴリズム を与える.このアルゴリズムは O (nm) 領域を用いて,全ての支配集合を解 1 つあたり O (k) 時間で列挙を行う.ここ で,k とは入力グラフの縮退数である.さらに,平面的グラフは縮退数が定数であることが知られている.したがっ て,提案アルゴリズムは平面的グラフ中の支配集合を解 1 つあたり定数時間で列挙する. 
(英) A dominating set is one of the fundamental graph structure, like clique, independent set, s-t path, and cut. It is known that there is a polynomial delay algorithm to enumerate theses minimal or maximal graph structures. However, it is open problem that there is a polynomial delay or amortized polynomial time algorithm to enumerate minimal dominating sets. In addition, enumeration of all dominating sets has not been paid much attention. In this paper, we enumerate all dominating sets not only minimal dominating sets. As a main result, we propose an efficient enumeration algorithm. This algorithm enumerates all dominating set in O (k) time per solution using O (nm) space, where k is degeneracy of an input graph. It is known that planar graphs have the constant degeneracy. Hence, the proposed algorithm enumerates all dominating set in constant time per solution.
キーワード (和) 支配集合 / 列挙アルゴリズム / ならし多項式時間 / 縮退数 / / / /  
(英) dominating sets / enumeration algorithm / amorized polynomial time / degeneracy / / / /  
文献情報 信学技報, vol. 117, no. 370, COMP2017-43, pp. 111-117, 2017年12月.
資料番号 COMP2017-43 
発行日 2017-12-14 (ISEC, COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード ISEC2017-89 COMP2017-43

研究会情報
研究会 ISEC COMP  
開催期間 2017-12-21 - 2017-12-22 
開催地(和) 高知工科大学永国寺キャンパス 
開催地(英) Eikokuji Campus, Kochi University of Technology 
テーマ(和) 一般 
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2017-12-ISEC-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) k-縮退グラフ中の支配集合の効率良い列挙 
サブタイトル(和)  
タイトル(英) Efficient Enumeration of Dominating Sets in K-Degenerate graphs 
サブタイトル(英)  
キーワード(1)(和/英) 支配集合 / dominating sets  
キーワード(2)(和/英) 列挙アルゴリズム / enumeration algorithm  
キーワード(3)(和/英) ならし多項式時間 / amorized polynomial time  
キーワード(4)(和/英) 縮退数 / degeneracy  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 栗田 和宏 / Kazuhiro Kurita / クリタ カズヒロ
第1著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: HU)
第2著者 氏名(和/英/ヨミ) 和佐 州洋 / Kunihiro Wasa / ワサ クニヒロ
第2著者 所属(和/英) 国立情報学研究所 (略称: NII)
National Institute of Informatics (略称: NII)
第3著者 氏名(和/英/ヨミ) 宇野 毅明 / Takeaki Uno / ウノ タケアキ
第3著者 所属(和/英) 国立情報学研究所 (略称: NII)
National Institute of Informatics (略称: NII)
第4著者 氏名(和/英/ヨミ) 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ
第4著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: HU)
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2017-12-22 14:40:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-ISEC2017-89,IEICE-COMP2017-43 
巻番号(vol) IEICE-117 
号番号(no) no.369(ISEC), no.370(COMP) 
ページ範囲 pp.111-117 
ページ数 IEICE-7 
発行日 IEICE-ISEC-2017-12-14,IEICE-COMP-2017-12-14 


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

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


IEICE / 電子情報通信学会