| Item type |
SIG Technical Reports(1) |
| 公開日 |
2022-09-08 |
| タイトル |
|
|
タイトル |
直並列グラフに含まれる極小誘導シュタイナー部分グラフの効率良い列挙に向けて |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Toward Efficiency Enumeration of Minimal Induced Steiner Subgraphs in Series-Parallel Graphs |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
豊橋技術科学大学大学院工学研究科 |
| 著者所属 |
|
|
|
法政大学理工学部 |
| 著者所属(英) |
|
|
|
en |
|
|
Computer Science and Engineering, Toyohashi University of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Faculty of Science and Engineering, Hosei University |
| 著者名 |
大野木, 駿
和佐, 州洋
|
| 著者名(英) |
Shun, Onogi
Kunihiro, Wasa
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
グラフ ???? = (???? , ????) とターミナル集合 ???? ⊆ ???? が与えられる．頂点集合 ???? ⊇ ???? によって誘導される部分グラフ ???? [????] が連結であるとき，????[????] は ISS であるという．S の任意の真部分集合 ????，に対して ???? [????] が ISS でないとき，???? [????] は MISS であるという．本研究では，入力グラフに含まれる MISS を漏れなく重複なく出力する列挙問題を考察した．本問題は，入力をスプリットグラフに制限しても難しいことが知られている [Conte et al., MFCS 2019]．本研究の主結果として，入力を直並列グラフに制限し，耳分解を利用して，解の集合がどのような構造をしているか詳細に解析した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Given a graph ???? = (???? , ????) with a terminal set ???? ⊆ ???? , a vertex subset ???? ⊆ ???? is an induced Steiner subgraph (ISS) if ???? [????] is connected and ???? ⊆ ????. Additionally, we say ???? is a minimal induced Steiner subgraph (MISS) if there is no proper subset ????, of ???? such that ???? [????,] is an ISS. In this paper, we consider an enumeration problem of MISSs in a graph. The task is to output all MISS in a graph without duplicates. This problem is known to be as hard as minimal hypergraph transversal enumeration even if we restrict inputs to split graphs[Conte et al., MFCS 2019]. As the main result of this paper, we give a detailed analysis of solution sets of MISSs in series-paralle graphs by using an ear decomsition of an input graph. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2022-AL-189,
号 2,
p. 1-7,
発行日 2022-09-08
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL22189002.pdf (941.5 kB)
