| Presentation | 2020-03-01 Metric Dimension on Some Classes of Chordal Graphs Ryoga Katoh, Remy Belmonte, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph theory / metric dimension / resolving sets / algorithms / treewidth / k-trees |
| Paper # | COMP2019-49 |
| Date of Issue | 2020-02-23 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2020/3/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | The University of Electro-Communications |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Metric Dimension on Some Classes of Chordal Graphs |
| Sub Title (in English) | |
| Keyword(1) | graph theory |
| Keyword(2) | metric dimension |
| Keyword(3) | resolving sets |
| Keyword(4) | algorithms |
| Keyword(5) | treewidth |
| Keyword(6) | k-trees |
| 1st Author's Name | Ryoga Katoh |
| 1st Author's Affiliation | The University of Electro-Communications(UEC) |
| 2nd Author's Name | Remy Belmonte |
| 2nd Author's Affiliation | The University of Electro-Communications(UEC) |
| Date | 2020-03-01 |
| Paper # | COMP2019-49 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-433 |
| Page | pp.pp.25-28(COMP), |
| #Pages | 4 |
| Date of Issue | 2020-02-23 (COMP) |