| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 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 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | 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. |
|
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Frequency Assignment / Distance-constrained Labeling / TSP / Graph Diameter / Parameterized Complexity / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 123, no. 227, COMP2023-12, pp. 9-11, Oct. 2023. | |
| Paper # | COMP2023-12 | |
| Date of Issue | 2023-10-17 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2023-12 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2023-10-24 - 2023-10-24 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Nagoya Univ. Venture Business Lab. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Theoretical Computer Science, etc |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2023-10-COMP |
| Language | English |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP |
| Sub Title (in English) | |
| Keyword(1) | Frequency Assignment |
| Keyword(2) | Distance-constrained Labeling |
| Keyword(3) | TSP |
| Keyword(4) | Graph Diameter |
| Keyword(5) | Parameterized Complexity |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Tesshu Hanaka |
| 1st Author's Affiliation | Kyushu University (Kyushu Univ.) |
| 2nd Author's Name | Hirotaka Ono |
| 2nd Author's Affiliation | Nagoya University (Nagoya Univ.) |
| 3rd Author's Name | Kosuke Sugiyama |
| 3rd Author's Affiliation | Nagoya University (Nagoya Univ.) |
| Speaker | Author-3 |
| Date Time | 2023-10-24 14:05:00 |
| Presentation Time | 35 minutes |
| Registration for | COMP |
| Paper # | COMP2023-12 |
| Volume (vol) | vol.123 |
| Number (no) | no.227 |
| Page | pp.9-11 |
| #Pages | 3 |
| Date of Issue | 2023-10-17 (COMP) |
[Return to Top Page]