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

講演抄録/キーワード
講演名 2020-10-23 17:05
Polynomial Delay Enumeration for Steiner Problems
Yasuaki KobayashiKyoto Univ.)・○Kazuhiro KuritaNII)・Kunihiro WasaToyohashi TechCOMP2020-17
抄録 (和) (まだ登録されていません) 
(英) Let $G = (V, E)$ be a undirected graph and let $W subseteq V$ be a set of terminals. A emph{Steiner subgraph} of $(G, W)$ is a subgraph of $G$ that contains all vertices of $W$ and there is a path between every pair of vertices of $W$ in the subgraph. We say that a Steiner subgraph is minimal if it has no proper Steiner subgraph. It is easy to observe that every minimal Steiner subgraph forms a tree, which is called a minimal Steiner tree. We propose a linear delay and polynomial space algorithm for enumerating all minimal Steiner trees of $(G, W)$, which improves a previously known polynomial delay enumeration algorithm in [Kimelfeld and Sagiv, Inf. Syst., 2008]. Our enumeration algorithm can be extended to other Steiner problems: minimal Steiner forests, minimal terminal Steiner trees, minimal directed Steiner trees. As another variant of the minimal Steiner subgraph problem, we study the problem of enumerating minimal induced Steiner subgraphs. We propose a polynomial delay and exponential space enumeration algorithm of minimal induced Steiner subgraphs for claw-free graphs, whereas the problem on general graphs is shown to be at least as hard as the problem of enumerating minimal transversals in hypergraphs. Contrary to these tractable results, we show that the problem of enumerating minimal group Steiner trees is at least as hard as the minimal transversal enumeration problem on hypergraphs.
キーワード (和) / / / / / / /  
(英) Minimal Steiner tree / Minimal Steiner forests / Enumeration problem / Polynomial delay / Graph algorithm / / /  
文献情報 信学技報, vol. 120, no. 209, COMP2020-17, pp. 39-46, 2020年10月.
資料番号 COMP2020-17 
発行日 2020-10-16 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2020-17

研究会情報
研究会 COMP  
開催期間 2020-10-23 - 2020-10-23 
開催地(和) 大阪大学 
開催地(英) Osaka Univ. 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2020-10-COMP 
本文の言語 英語 
タイトル(和)  
サブタイトル(和)  
タイトル(英) Polynomial Delay Enumeration for Steiner Problems 
サブタイトル(英)  
キーワード(1)(和/英) / Minimal Steiner tree  
キーワード(2)(和/英) / Minimal Steiner forests  
キーワード(3)(和/英) / Enumeration problem  
キーワード(4)(和/英) / Polynomial delay  
キーワード(5)(和/英) / Graph algorithm  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 小林 靖明 / Yasuaki Kobayashi / コバヤシ ヤスアキ
第1著者 所属(和/英) 京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.)
第2著者 氏名(和/英/ヨミ) 栗田 和宏 / Kazuhiro Kurita / クリタ カズヒロ
第2著者 所属(和/英) 国立情報学研究所 (略称: NII)
National Institute Informatics (略称: NII)
第3著者 氏名(和/英/ヨミ) 和佐 州洋 / Kunihiro Wasa / ワサ クニヒロ
第3著者 所属(和/英) 豊橋技術科学大学 (略称: 豊橋技科大)
Toyohashi University of Technology (略称: Toyohashi Tech)
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2020-10-23 17:05:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2020-17 
巻番号(vol) IEICE-120 
号番号(no) no.209 
ページ範囲 pp.39-46 
ページ数 IEICE-8 
発行日 IEICE-COMP-2020-10-16 


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

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


IEICE / 電子情報通信学会