| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-03-01 14:00 弦グラフの部分クラスの距離次元 ○加藤遼河・ベルモント レミー（電通大）  COMP2019-49 |
|
| 抄録 | （和） | グラフ$G$の頂点部分集合$S$で、任意の頂点対$u, v notin S$についてある頂点$w in S$が存在し、$u$-$w$間の距離と$v$-$w$間の距離が異なるようなものを$G$の分解集合とよび、また、取りうる分解集合の最小サイズを$G$の距離次元という。距離次元問題とは、グラフ$G$と整数$k$が与えられ、$G$が高々サイズ$k$の分解集合を持つか否かを問う問題で、NP完全であることが知られている。本稿では、$k$木における本問題の計算複雑性を研究の題材とし、制限した$k$木である$2$路に対する簡素な線形時間アルゴリズムを導入する。本アルゴリズムは本質的には Diaz et al.~[JCSS, 2017] による外平面グラフに対するアルゴリズムの能率化版である。 |
| （英） | The METRIC DIMENSION problem asks, given a graph $G$ and integer $k$, whether there exists a set $S$ of vertices of size at most $k$ such that, for any two vertices $u, v notin S$, there is a vertex $w in S$ such that the distance between $u$ and $w$ is different from the one between $v$ and $w$. This problem is known to be NP-complete. We study the complexity of the problem on $k$-trees and provide a simple linear-time algorithm for $2$-paths. Our algorithm is essentially a streamlined version of the one designed by Diaz et al. [JCSS, 2017] for outerplanar graphs. | |
| キーワード | （和） | グラフ理論 / 距離次元 / 分解集合 / アルゴリズム / 木幅 / k木 / / |
| （英） | graph theory / metric dimension / resolving sets / algorithms / treewidth / k-trees / / | |
| 文献情報 | 信学技報, vol. 119, no. 433, COMP2019-49, pp. 25-28, 2020年3月. | |
| 資料番号 | COMP2019-49 | |
| 発行日 | 2020-02-23 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2019-49 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2020-03-01 - 2020-03-01 |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2020-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 弦グラフの部分クラスの距離次元 |
| サブタイトル（和） | |
| タイトル（英） | Metric Dimension on Some Classes of Chordal Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ理論 / graph theory |
| キーワード(2)（和/英） | 距離次元 / metric dimension |
| キーワード(3)（和/英） | 分解集合 / resolving sets |
| キーワード(4)（和/英） | アルゴリズム / algorithms |
| キーワード(5)（和/英） | 木幅 / treewidth |
| キーワード(6)（和/英） | k木 / k-trees |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 加藤 遼河 / Ryoga Katoh / カトウ リョウガ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | ベルモント レミー / Remy Belmonte / ベルモント レミー |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2020-03-01 14:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2019-49 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.433 |
| ページ範囲 | pp.25-28 |
| ページ数 | 4 |
| 発行日 | 2020-02-23 (COMP) |
[研究会発表申込システムのトップページに戻る]