研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 1 - 20 件目／全件表示 >>

An improved spectral lower bound of treewidth 査読有り Open Access

Gima, T; Hanaka, T; Noro, K; Ono, H; Otachi, Y

INFORMATION PROCESSING LETTERS 188 巻 2025年2月

記述言語：英語出版者・発行元：Information Processing Letters

We show that for every n-vertex graph with at least one edge, its treewidth is greater than or equal to nλ2/(Δ+λ2)−1, where Δ and λ2 are the maximum degree and the second smallest Laplacian eigenvalue of the graph, respectively. This lower bound improves the one by Chandran and Subramanian [Inf. Process. Lett., 2003] and the subsequent one by the authors of the present paper [IEICE Trans. Inf. Syst., 2024]. The new lower bound is almost tight in the sense that there is an infinite family of graphs such that the lower bound is only 1 less than the treewidth for each graph in the family. Additionally, using similar techniques, we also present a lower bound of treewidth in terms of the largest and the second smallest Laplacian eigenvalues.

DOI： 10.1016/j.ipl.2024.106536

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints 査読有り Open Access

Kobayashi, Y; Kurita, K; Mann, K; Matsui, Y; Ono, H

ALGORITHMS 18 巻 ( 2 ) 2025年2月

担当区分：最終著者記述言語：英語出版者・発行元：Algorithms

In this paper, we consider the minimal vertex cover and minimal dominating sets with capacity and/or connectivity constraint enumeration problems. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algorithms run in polynomial delay, even on the class of d-claw free graphs. This result is extended for bounded-degree graphs and outputs in quasi-polynomial time on general graphs. To complement these algorithmic results, we show that the minimal connected vertex cover, minimal connected dominating set, and minimal capacitated vertex cover enumeration problems in 2-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs.

DOI： 10.3390/a18020112

Structural parameterizations of vertex integrity 査読有り Open Access

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

Shortest Longest-Path Graph Orientations for Trees 査読有り

Asahiro Y., Jansson J., Melkman A.A., Miyano E., Ono H., Xue Q., Yano Y., Zakov S.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 15538 LNCS 巻頁： 51 - 64 2025年

記述言語：英語出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Graph orientation transforms an undirected graph into a directed graph by assigning a direction to each edge. Among the many different optimization problems related to graph orientations, we focus here on the Shortest Longest-Path Orientation problem (SLPO) which is a generalization of the well-known Minimum Graph Coloring problem. The input to SLPO is an edge-bi-weighted undirected graph in which every edge has two (possibly different and not necessarily positive) lengths associated with its two directions. The goal is to find an orientation of the input graph that minimizes the length of the longest simple directed path. Recently, polynomial-time algorithms for simple graph structures such as paths, cycles, stars, and trees were proposed, and a new polynomial-time inapproximability result was also established. This paper presents (i) an O(n2logn)-time algorithm for trees, which is a significant improvement over the previously fastest algorithm whose time complexity was Ω(n14) and (ii) polynomial-time algorithms for trees and spiders that run even faster than (i) as long as every edge weight is an integer and the total weight of the edges is sub-exponential.

DOI： 10.1007/978-3-031-82670-2_5

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

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14752 LNCS 巻頁： 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 L1 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

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月

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.44225n)-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.41422n) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

DOI： 10.1016/j.dam.2024.04.006

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

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 S1,S2,…,Sk such that the size of each unit Si is r and the subgraph of G induced by Si 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 (MSO2). 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

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∗(2n) 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τ2+3.17τ), O∗(1.3161τ2+4τ), and O∗(1.1893τ2+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∗(2n/2)(=O(1.4143n)) time, which improves O∗(3n/3)(=O(1.4423n)) by a direct adjustment of the analysis of Bodlaender et al.’s O∗(3n/3)-time algorithm for Node Kayles.

DOI： 10.1007/s00453-023-01136-w

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 ΣP2 -complete in general, while the problem becomes NP-complete when an input graph is bipartite. We then present an O(2.1996n)-time algorithm for general graphs and an O(1.9181n)-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.4143n) time.

DOI： 10.1609/aaai.v38i18.30060

その他リンク： 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, 2O(τ2)nO(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 2O(τlogτ)nO(1)-time algorithm for Colored Arc Kayles. We then focus on Arc Kayles on trees, and propose a 2.2361τnO(1)-time algorithm. Furthermore, we show that the winner determination Arc Kayles on a tree can be solved in O(1.3831n) time, which improves the best-known running time O(1.4143n). 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

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

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP<sup>*</sup>

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

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年

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., maxu∈V(ℓ(u))−minu∈V(ℓ(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

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月

Sequentially Swapping Tokens: Further on Graph Classes

Kiya, H; Okada, Y; Ono, H; Otachi, Y

SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE 13878 巻頁： 222 - 235 2023年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the sequence of token swappings along the walk obtains one of the given token placements from the other one. This problem was introduced as Sequential Token Swapping by Yamanaka et al. [JGAA 2019], who showed that the problem is intractable in general but polynomial-time solvable for trees, complete graphs, and cycles. In this paper, we present a polynomial-time algorithm for block-cactus graphs, which include all previously known cases. We also present general tools for showing the hardness of problem on restricted graph classes such as chordal graphs and chordal bipartite graphs. We also show that the problem is hard on grids and king’s graphs, which are the graphs corresponding to the 15 puzzle and its variant with relaxed moves.

DOI： 10.1007/978-3-031-23101-8_15

その他リンク： https://dblp.uni-trier.de/db/conf/sofsem/sofsem2023.html#KiyaOOO23

Approximation Algorithms for the Longest Run Subsequence Problem. 査読有り

小野廣隆

Leibniz International Proceedings in Informatics (LIPIcs) 259 巻 2023年

Shortest Beer Path Queries Based on Graph Decomposition

Hanaka T., Ono H., Sadakane K., Sugiyama K.

Leibniz International Proceedings in Informatics, LIPIcs 283 巻頁： 37 - 20 2023年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Leibniz International Proceedings in Informatics, LIPIcs

Given a directed edge-weighted graph G = (V, E) with beer vertices B ⊆ V , a beer path between two vertices u and v is a path between u and v that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. We consider indexing problems on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size O(n) for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in O(α(n)) time, where α(·) is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size O(m + nr2) based on the triconnected component decomposition, where r is the size of the largest triconnected component. For a given query u, v ∈ V , our algorithm using the indexes can output the beer distance in query time O(α(m)). In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs.

DOI： 10.4230/LIPIcs.ISAAC.2023.37

その他リンク： https://dblp.uni-trier.de/db/conf/isaac/isaac2023.html#HanakaOSS23

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

Hanaka, T; Ono, H; Sugiyama, K

2023 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS, IPDPSW 頁： 308 - 313 2023年

出版者・発行元：2023 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2023

For an undirected graph G=(V, E) and a k-nonnegative integer vector p=(p_1, L˙, p_k), a mapping l: V → N ∪0 is called an L(p)-labeling of G if |l(u)-l(v)| ≥ p_d for any two distinct vertices u, v in V with distance d, and the maximum value of l(v) mid v in V is called the span of l. Originally, L(p)-labeling of G for p=(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. L(p) LABELING is the problem of finding the minimum span λp among L(p)-labelings of G, which is NP-hard for every non-zero p. L(p)-LABELING is well studied for specific p 's; in particular, many (exact or approximation) algorithms for general graphs or restricted classes of graphs are proposed for p=(2,1) or more generally p=(p, q). Unfortunately, most algorithms strongly depend on the values of p, and it is not apparent to extend algorithms for p to ones for another p' in general. In this paper, we give a simple polynomial-time reduction of L(p)-LABELING on graphs with a small diameter to METRIC (PATH) TSP, which enables us to use numerous results on (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 p under this framework is 1.5 -approximable, and it can be solved by the Held-Karp algorithm in O2^n n^2) time, where n is the number of vertices, and so on.

DOI： 10.1109/IPDPSW59300.2023.00059

　前のページ - 次のページ　

1
2
3
4
5
6
7
8
9
10
11
12