| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-10-24 14:05 Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP Tesshu Hanaka（Kyushu Univ.）・Hirotaka Ono・○Kosuke Sugiyama（Nagoya Univ.）  COMP2023-12 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | For an undirected graph $G=(V,E)$ and a $k$-nonnegative integer vector $bp=(p_1,ldots,p_k)$, a mapping $lcolon Vto mathbb{N}cup {0}$ is called an $L(bp)$-labeling of $G$ if $left| l(u)-l(v) right|geq p_d$ for any two distinct vertices $u,vin V$ with distance $d$, and the maximum value of ${l(v)mid vin V}$ is called the span of $l$. Originally, $L(bp)$-labeling of $G$ for $bp=(2,1)$ is introduced in the context of frequency assignment in radio networks, where ‘close’ transmitters must receive different frequencies and ‘very close’ transmitters must receive frequencies that are at least two frequencies apart so that they can avoid interference. textsc{$L(bp)$-Labeling} is the problem of finding the minimum span $lambda_{bp}$ among $L(bp)$-labelings of $G$, which is NP-hard for every non-zero $bp$. textsc{$L(bp)$-Labeling} is well studied for specific $bp$'s; in particular, many (exact or approximation) algorithms for general graphs or restricted classes of graphs are proposed for $bp=(2,1)$ or more generally $bp=(p,q)$. Unfortunately, most algorithms strongly depend on the values of $bp$, and it is not apparent to extend algorithms for $bp$ to ones for another $bp'$ in general. In this paper, we show a polynomial-time reduction of textsc{$L(bp)$-Labeling} on graphs with a small diameter to textsc{Metric (Path) TSP}, which enables us to use numerous results on textsc{(Metric) TSP}. On the practical side, we can utilize various high-performance heuristics for TSP, such as Concordo and LKH, to solve our problem. On the theoretical side, we can see that the problem for any $bp$ under this framework is 1.5-approximable, and it can be solved in $O(2^n n^2)$ time, where $n$ is the number of vertices, and so on. |
|
| キーワード | （和） | / / / / / / / |
| （英） | Frequency Assignment / Distance-constrained Labeling / TSP / Graph Diameter / Parameterized Complexity / / / | |
| 文献情報 | 信学技報, vol. 123, no. 227, COMP2023-12, pp. 9-11, 2023年10月. | |
| 資料番号 | COMP2023-12 | |
| 発行日 | 2023-10-17 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-12 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2023-10-24 - 2023-10-24 |
| 開催地（和） | 名古屋大学 VBL |
| 開催地（英） | Nagoya Univ. Venture Business Lab. |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2023-10-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / Frequency Assignment |
| キーワード(2)（和/英） | / Distance-constrained Labeling |
| キーワード(3)（和/英） | / TSP |
| キーワード(4)（和/英） | / Graph Diameter |
| キーワード(5)（和/英） | / Parameterized Complexity |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 土中 哲秀 / Tesshu Hanaka / ハナカ テッシュウ |
| 第1著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ |
| 第2著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 杉山 康恭 / Kosuke Sugiyama / スギヤマ コウスケ |
| 第3著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第3著者 |
| 発表日時 | 2023-10-24 14:05:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-12 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.227 |
| ページ範囲 | pp.9-11 |
| ページ数 | 3 |
| 発行日 | 2023-10-17 (COMP) |
[研究会発表申込システムのトップページに戻る]