| 講演名 | 2023-10-24 Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP 土中 哲秀(九大), 小野 廣隆(名大), 杉山 康恭(名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | 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 thatthey 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 AssignmentDistance-constrained LabelingTSPGraph DiameterParameterized Complexity |
| 資料番号 | COMP2023-12 |
| 発行日 | 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 |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / Frequency AssignmentDistance-constrained LabelingTSPGraph DiameterParameterized Complexity |
| 第 1 著者 氏名（和/英） | 土中 哲秀 / Tesshu Hanaka |
| 第 1 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 2 著者 氏名（和/英） | 小野 廣隆 / Hirotaka Ono |
| 第 2 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 3 著者 氏名（和/英） | 杉山 康恭 / Kosuke Sugiyama |
| 第 3 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 発表年月日 | 2023-10-24 |
| 資料番号 | COMP2023-12 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-227 |
| ページ範囲 | pp.9-11(COMP), |
| ページ数 | 3 |
| 発行日 | 2023-10-17 (COMP) |