講演抄録/キーワード |
講演名 |
2023-05-11 14:20
直並列グラフに含まれる極小誘導シュタイナー部分グラフの列挙 ○大野木 駿(豊橋技科大)・和佐州洋(法政大) COMP2023-5 |
抄録 |
(和) |
グラフ $G=(V,E)$ とターミナル集合 $W$ が与えられる.
頂点集合 $S supseteq W$ によって誘導される部分グラフ $G[S]$ が連結であるとき,$G[S]$ は ISS であるという.
$S$ の任意の真部分集合 $S'$ に対して $G[S']$ が ISS でないとき,$G[S]$ は MISS であるという.
本研究では,入力グラフに含まれる MISS を全て,重複なく出力する列挙問題について考察した.
本問題は,入力をスプリットグラフに制限しても難しいことが知られている [Conte et al., MFCS 2019].
本研究の主結果として,直並列グラフに対する MISS の列挙アルゴリズムを開発した.本アルゴリズムは,分割法をベースとしている. |
(英) |
Given a graph $G = (V, E)$ with a terminal set $W subseteq V$,
a vertex subset $S subseteq V$ is an emph{induced Steiner subgraph (ISS)} if $G[S]$ is connected and $W subseteq S$.
Additionally, we say $S$ is a emph{minimal induced Steiner subgraph (MISS)} if there is no proper subset $S'$ of $S$ such that $G[S']$ 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 develop an enumeration algorithm for MISSs in a series-parallel graph based on the binary partition method. |
キーワード |
(和) |
グラフアルゴリズム / 列挙 / 誘導シュタイナーグラフ / 直並列グラフ / / / / |
(英) |
Graph algorithms / enumeration / induced Steiner subgraphs / series-parallel graphs / / / / |
文献情報 |
信学技報, vol. 123, no. 12, COMP2023-5, pp. 22-28, 2023年5月. |
資料番号 |
COMP2023-5 |
発行日 |
2023-05-03 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2023-5 |