@techreport{oai:ipsj.ixsq.nii.ac.jp:00220140,
 author = {大野木, 駿 and 和佐, 州洋 and Shun, Onogi and Kunihiro, Wasa},
 issue = {2},
 month = {Sep},
 note = {グラフ ???? = (???? , ????) とターミナル集合 ???? ⊆ ???? が与えられる．頂点集合 ???? ⊇ ???? によって誘導される部分グラフ ???? [????] が連結であるとき，????[????] は ISS であるという．S の任意の真部分集合 ????，に対して ???? [????] が ISS でないとき，???? [????] は MISS であるという．本研究では，入力グラフに含まれる MISS を漏れなく重複なく出力する列挙問題を考察した．本問題は，入力をスプリットグラフに制限しても難しいことが知られている [Conte et al., MFCS 2019]．本研究の主結果として，入力を直並列グラフに制限し，耳分解を利用して，解の集合がどのような構造をしているか詳細に解析した．, 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.},
 title = {直並列グラフに含まれる極小誘導シュタイナー部分グラフの効率良い列挙に向けて},
 year = {2022}
}