| 講演名 | 2023-05-11 直並列グラフに含まれる極小誘導シュタイナー部分グラフの列挙 大野木 駿(豊橋技科大), 和佐 州洋(法政大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフ $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 |
| 資料番号 | COMP2023-5 |
| 発行日 | 2023-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2023/5/10(から2日開催) |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 委員長氏名（和） | 宇野 裕之(大阪公立大) |
| 委員長氏名（英） | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| 副委員長氏名（和） | 来嶋 秀治(滋賀大) |
| 副委員長氏名（英） | Shuji Kijima(Shiga Univ.) |
| 幹事氏名（和） | 和佐 州洋(法政大) / 横井 優(NII) |
| 幹事氏名（英） | Kunihiro Wasa(Hosei Univ.) / Yu Yokoi(NII) |
| 幹事補佐氏名（和） | 安藤 映(専修大) |
| 幹事補佐氏名（英） | Ei Ando(Senshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 直並列グラフに含まれる極小誘導シュタイナー部分グラフの列挙 |
| サブタイトル（和） | |
| タイトル（英） | Enumeration of Minimal Induced Steiner Subgraph in a Series-Parallel Graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフアルゴリズム / Graph algorithms |
| キーワード(2)（和/英） | 列挙 / enumeration |
| キーワード(3)（和/英） | 誘導シュタイナーグラフ / induced Steiner subgraphs |
| キーワード(4)（和/英） | 直並列グラフ / series-parallel graphs |
| 第 1 著者 氏名（和/英） | 大野木 駿 / Shun Onogi |
| 第 1 著者 所属（和/英） | 豊橋技術科学大学(略称：豊橋技科大) Toyohashi University of Technology(略称：TUT) |
| 第 2 著者 氏名（和/英） | 和佐 州洋 / Kunihiro Wasa |
| 第 2 著者 所属（和/英） | 法政大学(略称：法政大) Hosei University(略称：Hosei Univ.) |
| 発表年月日 | 2023-05-11 |
| 資料番号 | COMP2023-5 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-12 |
| ページ範囲 | pp.22-28(COMP), |
| ページ数 | 7 |
| 発行日 | 2023-05-03 (COMP) |