| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-10-24 13:30 Proper interval graphの安全全支配集合問題に対するアルゴリズム ○荒木 徹・會田康文（群馬大）  COMP2023-11 |
|
| 抄録 | （和） | グラフ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 / / / / | |
| 文献情報 | 信学技報, vol. 123, no. 227, COMP2023-11, pp. 1-8, 2023年10月. | |
| 資料番号 | COMP2023-11 | |
| 発行日 | 2023-10-17 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-11 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2023-10-24 - 2023-10-24 |
| 開催地（和） | 名古屋大学 VBL |
| 開催地（英） | Nagoya Univ. Venture Business Lab. |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2023-10-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 荒木 徹 / Toru Araki / アラキ トオル |
| 第1著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 會田 康文 / Yasufumi Aita / アイタ ヤスフミ |
| 第2著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-10-24 13:30:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-11 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.227 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2023-10-17 (COMP) |
[研究会発表申込システムのトップページに戻る]