論文 - 小野　廣隆

Faster winner determination algorithms for (Colored) Arc Kayles

Hanaka, T; Kiya, H; Lampis, M; Ono, H; Yoshiwatari, K

JOURNAL OF COMPUTER AND SYSTEM SCIENCES   156 巻   2026年3月

　詳細を見る

出版者・発行元：Journal of Computer and System Sciences  

ARC KAYLES and COLORED ARC KAYLES are generalized versions of well-studied combinatorial games CRAM and DOMINEERING, respectively. In ARC KAYLES, two players alternately choose an edge to remove with its adjacent edges, and the player who cannot move is the loser. COLORED ARC KAYLES is similarly played on a graph with edges colored in black, white, or gray, in which the black (resp., white) player can choose only a gray or black (resp., white) edge. For ARC KAYLES, the vertex cover number τ (i.e., the minimum size of a vertex cover) is an essential invariant because it is known that twice the vertex cover number upper bounds the number of turns of ARC KAYLES, and for the winner determination of (COLORED) ARC KAYLES, 2^O(τ²)n^O(1)-time algorithms are known, where n is the number of vertices. In this paper, we first give a polynomial kernel for COLORED ARC KAYLES parameterized by τ, which leads to a faster 2^{O(τlog⁡τ)}n^O(1)-time algorithm for COLORED ARC KAYLES. We then focus on ARC KAYLES on trees, and propose a 2.2361^τn^O(1)-time algorithm. Furthermore, we show that determining the winner of ARC KAYLES on a tree can be done in O(1.3831ⁿ) time, which improves the best-known running time of O(1.4143ⁿ). Finally, we show that COLORED ARC KAYLES is NP-hard, the first hardness result in the family of the above games.

DOI： 10.1016/j.jcss.2025.103716

Web of Science

Scopus

Approximability of Longest Run Subsequence and Complementary Minimization Problems Open Access

Asahiro Y., Jansson J., Lu S., Ono H., Tanaka S., Gong M., Lin G., Miyano E., Saitoh T.

Leibniz International Proceedings in Informatics Lipics   344 巻   2025年8月

　詳細を見る

出版者・発行元：Leibniz International Proceedings in Informatics Lipics  

We study the polynomial-time approximability of the Longest Run Subsequence problem (LRS for short) and its complementary minimization variant Minimum Run Subsequence Deletion problem (MRSD for short). For a string S = s1 · · · sn over an alphabet Σ, a subsequence S^′ of S is S^′ = si<inf>1</inf> · · · si<inf>p</inf>, such that 1 ≤ i1 < i2 < . . . < ip ≤ |S|. A run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S^′ of S is a subsequence of S in which every symbol σ ∈ Σ occurs in at most one run. The co-subsequence S^′ of the subsequence S^′ = si<inf>1</inf> · · · si<inf>p</inf> in S is the subsequence obtained by deleting all the characters in S^′ from S, i.e., S^′ = sj<inf>1</inf> · · · sj<inf>n</inf>−<inf>p</inf> such that j1 < j2 < . . . < jn−p and {j1, . . ., jn−p} = {1, . . ., n} \ {i1, . . ., ip}. Given a string S, the goal of LRS (resp., MRSD) is to find a run subsequence S^∗ of S such that the length |S^∗| is maximized (resp., the number |S^∗| of deleted symbols from S is minimized) over all the run subsequences of S. Let k be the maximum number of symbol occurrences in the input S. It is known that LRS and MRSD are APX-hard even if k = 2. In this paper, we show that LRS can be approximated in polynomial time within factors of (k + 2)/3 for k = 2 or 3, and 2(k + 1)/5 for every k ≥ 4. Furthermore, we show that MRSD can be approximated in linear time within a factor of (k + 4)/4 if k is even and (k + 3)/4 if k is odd.

DOI： 10.4230/LIPIcs.WABI.2025.3

Open Access

Scopus

Enumeration of Ordered Trees with Leaf Restrictions Open Access

Kobayashi Y., Köppl D., Matsui Y., Ono H., Saitoh T., Uno Y.

Openaccess Series in Informatics   132 巻   2025年8月

　詳細を見る

出版者・発行元：Openaccess Series in Informatics  

An α-ary tree for a constant α ≥ 2 is a rooted tree in which each node has at most α children. A node having no children is called a leaf. For a given rooted tree and a node v, the number of edges from the root to v is called the depth of v. We call a vector w = (w1, w2, . . ., w<inf>d</inf>) of nonnegative integers an (α-ary) distribution if there is an α-ary tree T such that the number of leaves at each depth i ∈ [1..d] in T is wi. Although not every vector of nonnegative integers is a distribution, a distribution can be associated with many α-ary trees. In this paper, we present an algorithm to enumerate all α-ary trees for a given distribution. Our algorithm reports the first tree in O(d + ∑d<inf>i</inf><inf>=1</inf> wi) time, and then each subsequent α-ary tree in O(max^d<inf>i</inf><inf>=1</inf> wi) time by representing each tree as the difference from the previous one. The algorithm can be restricted to computing all trees that are full, i.e., trees whose nodes have exactly α or no children.

DOI： 10.4230/OASIcs.Grossi.2025.8

Open Access

Scopus

Structural parameterizations of vertex integrity 査読有り

Gima, T; Hanaka, T; Kobayashi, Y; Murai, R; Ono, H; Otachi, Y

THEORETICAL COMPUTER SCIENCE   1024 巻   2025年1月

　詳細を見る

記述言語：英語   出版者・発行元：Theoretical Computer Science  

The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts. We also show that the vertex integrity can be approximated within an O(log⁡opt) factor.

DOI： 10.1016/j.tcs.2024.114954

Web of Science

Scopus

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models 査読有り

Honorato-Droguett, N; Kurita, K; Hanaka, T; Ono, H

FRONTIERS OF ALGORITHMICS, IJTCS-FAW 2024   14752 巻   頁： 66 - 78   2025年

　詳細を見る

記述言語：英語   出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics  

We propose a new model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing operations. As a graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. In this paper, we focus on interval graphs as an intersection graph. We give a linear-time algorithm to find the total moving distance for transforming an interval graph into a complete graph. The concept of this algorithm can be applied for (i) transforming a unit square graph into a complete graph over L<inf>1</inf> distance and (ii) attaining the existence of a k-clique on unit interval graphs. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.

DOI： 10.1007/978-981-97-7752-5_5

Web of Science

Scopus

Hardness Results on Generalized Puyo Puyo Open Access

Eto H., Kiya H., Ono H.

Journal of Information Processing   33 巻 ( 0 ) 頁： 1077 - 1091   2025年

　詳細を見る

記述言語：英語   出版者・発行元：一般社団法人 情報処理学会  

Puyo Puyo is a Tetris-like falling-block video game, which has been played in Japan more than 30 years. In Tetris, tetrominoes fall on the board, whereas colored and colorless “puyo”s fall in Puyo Puyo. The clearing rule in Tetris is to fill a line (row) of the board, whereas that in Puyo Puyo is to make a cluster with a size of at least 4 puyos with a single color. A colorless puyo is cleared only when a colored puyo touching it is cleared. Due to this clearing rule, a clearing chain phenomenon arises, which is a unique nature of Puyo Puyo. In this paper, we investigate the computational complexity of a generalized Puyo Puyo, where the size of the board and the number of colors are arbitrary, but the falling sequence of puyos is given in an offline manner. We focus on two algorithmic problems in the generalized Puyo Puyo. One is the problem of finding a clearing chain with the longest length for a given board and a falling sequence of puyos, and the other is the problem of deciding whether a given board and a falling sequence of puyos can clear all the puyos, or not. Both problems are already known to be NP-complete. The former problem, the longest clearing chain problem, is shown to be NP-complete even if the number of colors is 4. The latter problem, the all-clear problem, is also shown to be NP-complete even if the number of colors is 2. In this paper, we strengthen these results: (1) The longest clearing chain problem is NP-complete even if the number of colors is 2. (2) The longest clearing chain cannot be approximated within a factor better than any polynomial of the falling sequence length in polynomial time unless P = NP.

DOI： 10.2197/ipsjjip.33.1077

Open Access

Scopus

CiNii Research

Structural Parameters for Steiner Orientation Open Access

Hanaka T., Lampis M., Melissinos N., Nemery E., Ono H., Vasilakis M.

Leibniz International Proceedings in Informatics Lipics   359 巻   2025年

　詳細を見る

出版者・発行元：Leibniz International Proceedings in Informatics Lipics  

We consider the Steiner Orientation problem, where we are given as input a mixed graph G = (V, E, A) and a set of k demand pairs (si, ti), i ∈ [k]. The goal is to orient the undirected edges of G in a way that the resulting directed graph has a directed path from si to ti for all i ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following: 1. We show that Steiner Orientation is NP-complete on instances where the underlying graph has feedback vertex number 2, treewidth 2, pathwidth 3, and vertex integrity 6. 2. We present an XP algorithm parameterized by vertex cover number vc of complexity n^O(^vc2). Furthermore, we show that this running time is essentially optimal by proving that a running time of n^o(^vc2) would refute the ETH. 3. We consider parameterizations by the number of undirected or directed edges (|E| or |A|) and we observe that the trivial 2^|E^|n^O⁽¹⁾-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2^O(|A|⁾n^O⁽¹⁾-time algorithm. In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw + k (FPT), distance to clique (FPT), and vc + k (FPT with a polynomial kernel).

DOI： 10.4230/LIPIcs.ISAAC.2025.38

Open Access

Scopus

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kanae Yoshiwatari: Computational complexity of Turning Tiles 査読有り

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kanae Yoshiwatari

International Journal of Game Theory   53 巻 ( 4 )   2024年10月

　詳細を見る

記述言語：英語  

DOI： 10.1007/s00182-024-00908-0

Polynomial-time equivalences and refined algorithms for longest common subsequence variants 査読有り Open Access

Asahiro, Y; Jansson, J; Lin, GH; Miyano, E; Ono, H; Utashima, T

DISCRETE APPLIED MATHEMATICS   353 巻   頁： 44 - 64   2024年8月

　詳細を見る

記述言語：英語   出版者・発行元：Discrete Applied Mathematics  

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS: the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (RBLCS), the MULTISET-RESTRICTED COMMON SUBSEQUENCE problem (MRCS), the TWO-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (2FLCS), and the ONE-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (1FLCS). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225ⁿ)-time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and poly(n). Here, we first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422ⁿ) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422ⁿ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

DOI： 10.1016/j.dam.2024.04.006

Web of Science

Scopus

Grouped domination parameterized by vertex cover, twin cover, and beyond 査読有り

Hanaka, T; Ono, H; Otachi, Y; Uda, S

THEORETICAL COMPUTER SCIENCE   996 巻   2024年5月

　詳細を見る

記述言語：英語   出版者・発行元：Theoretical Computer Science  

A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S<inf>1</inf>,S<inf>2</inf>,…,S<inf>k</inf> such that the size of each unit S<inf>i</inf> is r and the subgraph of G induced by S<inf>i</inf> is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets (r=1), paired dominating sets (r=2), and connected dominating sets (r is arbitrary and k=1). In this paper, we investigate the computational complexity of r-GROUPED DOMINATING SET, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r-GROUPED DOMINATING SET is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r-GROUPED DOMINATING SET for every fixed r>0 is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r-GROUPED DOMINATING SET is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic (MSO<inf>2</inf>). This fixed-parameter tractability is good news, but the running time is not practical. We then design an O^⁎(min⁡{(2τ(r+1))^τ,(2τ)^2τ})-time algorithm for general r≥2, where τ is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., r∈{2,3}, we can speed up the algorithm, whose running time becomes O^⁎((r+1)^τ). We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r-GROUPED DOMINATING SET.

DOI： 10.1016/j.tcs.2024.114507

Web of Science

Scopus

Winner Determination Algorithms for Graph Games with Matching Structures

Hanaka, T; Kiya, H; Ono, H; Yoshiwatari, K

ALGORITHMICA   86 巻 ( 3 ) 頁： 808 - 824   2024年3月

　詳細を見る

掲載種別：研究論文（学術雑誌）   出版者・発行元：Algorithmica  

Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, while gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in O^∗(2ⁿ) time by a simple algorithm, where n is the order of the input graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O^∗(1.4143^{τ²⁺^3.17^τ}), O^∗(1.3161^{τ²⁺⁴^τ}), and O^∗(1.1893^{τ²⁺^6.34^τ}), respectively, where τ is the vertex cover number. Furthermore, we present an O^∗((n/ν+1)^ν)-time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O^∗(2^n/2)(=O(1.4143ⁿ)) time, which improves O^∗(3^n/3)(=O(1.4423ⁿ)) by a direct adjustment of the analysis of Bodlaender et al.’s O^∗(3^n/3)-time algorithm for Node Kayles.

DOI： 10.1007/s00453-023-01136-w

Web of Science

Scopus

Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover Open Access

Horiyama T., Kobayashi Y., Ono H., Seto K., Suzuki R.

Proceedings of the Aaai Conference on Artificial Intelligence   38 巻 ( 18 ) 頁： 20726 - 20734   2024年

　詳細を見る

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Proceedings of the Aaai Conference on Artificial Intelligence  

The uniqueness of an optimal solution to a combinatorial optimization problem attracts many fields of researchers’ attention because it has a wide range of applications, it is related to important classes in computational complexity, and an instance with only one solution is often critical for algorithm designs in theory. However, as the authors know, there is no major benchmark set consisting of only instances with unique solutions, and no algorithm generating instances with unique solutions is known; a systematic approach to getting a problem instance guaranteed having a unique solution would be helpful. A possible approach is as follows: Given a problem instance, we specify a small part of a solution in advance so that only one optimal solution meets the specification. This paper formulates such a “pre-assignment” approach for the vertex cover problem as a typical combinatorial optimization problem and discusses its computational complexity. First, we show that the problem is Σ^P<inf>2</inf> -complete in general, while the problem becomes NP-complete when an input graph is bipartite. We then present an O(2.1996ⁿ)-time algorithm for general graphs and an O(1.9181ⁿ)-time algorithm for bipartite graphs, where n is the number of vertices. The latter is based on an FPT algorithm with O^∗(3.6791^τ) time for vertex cover number τ. Furthermore, we show that the problem for trees can be solved in O(1.4143ⁿ) time.

DOI： 10.1609/aaai.v38i18.30060

Open Access

Scopus

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#HoriyamaK0SS24

Faster Winner Determination Algorithms for (Colored) Arc Kayles

Hanaka, T; Kiya, H; Lampis, M; Ono, H; Yoshiwatari, K

SOFSEM 2024: THEORY AND PRACTICE OF COMPUTER SCIENCE   14519 巻   頁： 297 - 310   2024年

　詳細を見る

出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics  

Arc Kayles and Colored Arc Kayles, two-player games on a graph, are generalized versions of well-studied combinatorial games Cram and Domineering, respectively. In Arc Kayles, players alternately choose an edge to remove with its adjacent edges, and the player who cannot move is the loser. Colored Arc Kayles is similarly played on a graph with edges colored in black, white, or gray, while the black (resp., white) player can choose only a gray or black (resp., white) edge. For Arc Kayles, the vertex cover number (i.e., the minimum size of a vertex cover) is an essential invariant because it is known that twice the vertex cover number upper bounds the number of turns of Arc Kayles, and for the winner determination of (Colored) Arc Kayles, 2^O^(τ2)n^O(1)-time algorithms are known, where τ is the vertex cover number and n is the number of vertices. In this paper, we first give a polynomial kernel for Colored Arc Kayles parameterized by τ, which leads to a faster 2^O(τlogτ)n^O(1)-time algorithm for Colored Arc Kayles. We then focus on Arc Kayles on trees, and propose a 2.2361^τn^O(1)-time algorithm. Furthermore, we show that the winner determination Arc Kayles on a tree can be solved in O(1.3831ⁿ) time, which improves the best-known running time O(1.4143ⁿ). Finally, we show that Colored Arc Kayles is NP-hard, the first hardness result in the family of the above games.

DOI： 10.1007/978-3-031-52113-3_21

Web of Science

Scopus

Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs

Hanaka T., Ikeyama A., Ono H.

Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics   14461 LNCS 巻 ( 3 ) 頁： 392 - 405   2024年

　詳細を見る

掲載種別：研究論文（学術雑誌）   出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics  

Fractional hedonic games are coalition formation games where the utility of a player is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition formation games that can be succinctly represented. Due to their applicability in network clustering and their relationship to graph hedonic games, fractional hedonic games have been extensively studied from various perspectives. However, finding welfare-maximizing partitions in fractional hedonic games is a challenging task due to the nonlinearity of utilities. In fact, it has been proven to be NP-hard in general and can be solved in polynomial time only for a limited number of graph classes, such as trees. This paper presents (pseudo)polynomial-time algorithms to compute welfare-maximizing partitions in fractional hedonic games on tree-like graphs. We consider two types of social welfare measures: utilitarian and egalitarian. Tree-like graphs refer to graphs with bounded treewidth and block graphs. An NP-hardness result demonstrates that the pseudopolynomial-time solvability is the best possible under the assumption P ≠ NP.

DOI： 10.1007/978-3-031-49611-0_28

Web of Science

Scopus

Structural Parameterizations of Vertex Integrity [Best Paper]

Gima, T; Hanaka, T; Kobayashi, Y; Murai, R; Ono, H; Otachi, Y

WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024   14549 巻   頁： 406 - 420   2024年

　詳細を見る

出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics  

The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.

DOI： 10.1007/978-981-97-0566-5_29

Web of Science

Scopus

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP^*

International Journal of Networking and Computing   14 巻 ( 1 ) 頁： 26 - 39   2024年

　詳細を見る

記述言語：英語   出版者・発行元：IJNC編集委員会  

DOI： 10.15803/ijnc.14.1_26

CiNii Research

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP.

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

International Journal of Networking and Computing   14 巻 ( 1 ) 頁： 26 - 39   2024年

　詳細を見る

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2303.01290

その他リンク： https://dblp.uni-trier.de/db/journals/ijnc/ijnc14.html#HanakaOS24

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP 査読有り

土中 哲秀, 小野 廣隆

Int. J. Netw. Comput.   14(1) 巻   頁： 26 - 39   2024年

　詳細を見る

CiNii Research

An 8-approximation algorithm for <i>L</i>(2,1)-labeling of unit disk graphs

Ono, H; Yamanaka, H

DISCRETE APPLIED MATHEMATICS   341 巻   頁： 93 - 101   2023年12月

　詳細を見る

掲載種別：研究論文（学術雑誌）   出版者・発行元：Discrete Applied Mathematics  

Given a graph G=(V,E), an L(2,1)-labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u,v), |ℓ(u)−ℓ(v)|≥2 if u and v are adjacent, and ℓ(u)≠ℓ(v) if u and v are at distance 2. The L(2,1)-labeling problem is to minimize the range of ℓ (i.e., max<inf>u∈V</inf>(ℓ(u))−min<inf>u∈V</inf>(ℓ(u))+1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L(2,1)-labeling of unit disk graphs.

DOI： 10.1016/j.dam.2023.07.012

Web of Science

Scopus

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

IPDPS Workshops 2023   abs/2303.01290 巻   2023年5月

　詳細を見る

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.48550/arXiv.2303.01290