| 講演名 | 2023-10-24 Proper interval graphの安全全支配集合問題に対するアルゴリズム 荒木 徹(群馬大), 會田 康文(群馬大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフGの頂点の部分集合Sは，任意の頂点vに対して，vに隣接するSの頂点が存在するとき，全支配集合であるという。さらに，任意の頂点vに対して，Sのある頂点uが存在して，uvが辺でありかつ (S - {u}) cup {v} がGの全支配集合であるとき，SをGの安全全支配集合であるという。本発表ではproper interval graphに対して，最小の安全全支配集合を求めるO(m)時間アルゴリズムを提案する。ここでmはグラフの辺の数である。 |
| 抄録(英) | A subset $S$ of vertices of $G$ is a total dominating set if, for any vertex $v$, there is a vertex in $S$ adjacent to $v$. A total dominating set $S$ is a secure total dominating set if, for any vertex $v notin S$, there is a vertex $u in S$ such that $uv$ is an edge and $(S setminus {u}) cup {v}$ is also a total dominating set. In this paper, we design an $O(m)$-time algorithm for computing a minimum secure total dominating set in a proper interval graph, where $m$ is the number of edges. |
| キーワード(和) | 安全全支配集合 / 支配集合 / proper intervalグラフ / 多項式時間アルゴリズム |
| キーワード(英) | secure total dominating set / dominating set / proper interval graph / polynomial-time algorithm |
| 資料番号 | COMP2023-11 |
| 発行日 | 2023-10-17 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2023/10/24(から1日開催) |
| 開催地（和） | 名古屋大学 VBL |
| 開催地（英） | Nagoya Univ. Venture Business Lab. |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 委員長氏名（和） | 宇野 裕之(大阪公立大) |
| 委員長氏名（英） | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| 副委員長氏名（和） | 来嶋 秀治(滋賀大) |
| 副委員長氏名（英） | Shuji Kijima(Shiga Univ.) |
| 幹事氏名（和） | 和佐 州洋(法政大) / 横井 優(東工大) |
| 幹事氏名（英） | Kunihiro Wasa(Hosei Univ.) / Yu Yokoi(Tokyo Inst. of Tech) |
| 幹事補佐氏名（和） | 安藤 映(専修大) |
| 幹事補佐氏名（英） | Ei Ando(Senshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Proper interval graphの安全全支配集合問題に対するアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An algorithm for the secure total domination problem in proper interval graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 安全全支配集合 / secure total dominating set |
| キーワード(2)（和/英） | 支配集合 / dominating set |
| キーワード(3)（和/英） | proper intervalグラフ / proper interval graph |
| キーワード(4)（和/英） | 多項式時間アルゴリズム / polynomial-time algorithm |
| 第 1 著者 氏名（和/英） | 荒木 徹 / Toru Araki |
| 第 1 著者 所属（和/英） | 群馬大学(略称：群馬大) Gunma University(略称：Gunma Univ.) |
| 第 2 著者 氏名（和/英） | 會田 康文 / Yasufumi Aita |
| 第 2 著者 所属（和/英） | 群馬大学(略称：群馬大) Gunma University(略称：Gunma Univ.) |
| 発表年月日 | 2023-10-24 |
| 資料番号 | COMP2023-11 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-227 |
| ページ範囲 | pp.1-8(COMP), |
| ページ数 | 8 |
| 発行日 | 2023-10-17 (COMP) |