Faculty Profiles - ONO Hirotaka

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 Vol. 344 2025.8

Publisher：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

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 Vol. 132 2025.8

Publisher：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(maxd<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

Structural parameterizations of vertex integrity Reviewed

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

THEORETICAL COMPUTER SCIENCE Vol. 1024 2025.1

Language：English Publisher：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

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models Reviewed

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

FRONTIERS OF ALGORITHMICS, IJTCS-FAW 2024 Vol. 14752 page： 66 - 78 2025

Language：English Publisher：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

Hardness Results on Generalized Puyo Puyo Open Access

Eto Hiroshi, Kiya Hironori, Ono Hirotaka

Journal of Information Processing Vol. 33 ( 0 ) page： 1077 - 1091 2025

Language：English Publisher：Information Processing Society of Japan

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

Structural Parameters for Steiner Orientation

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

Leibniz International Proceedings in Informatics Lipics Vol. 359 2025

Publisher：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 nO(vc2). Furthermore, we show that this running time is essentially optimal by proving that a running time of no(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|nO(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2O(|A|)nO(1)-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

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kanae Yoshiwatari: Computational complexity of Turning Tiles Reviewed

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

International Journal of Game Theory Vol. 53 ( 4 ) 2024.10

Polynomial-time equivalences and refined algorithms for longest common subsequence variants Reviewed Open Access

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

DISCRETE APPLIED MATHEMATICS Vol. 353 page： 44 - 64 2024.8

Language：English Publisher：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 Reviewed

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

THEORETICAL COMPUTER SCIENCE Vol. 996 2024.5

Language：English Publisher：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

Winner Determination Algorithms for Graph Games with Matching Structures.

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

Algorithmica Vol. 86 ( 3 ) page： 808 - 824 2024.3

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

Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki

AAAI Vol. 38 ( 18 ) page： 20726 - 20734 2024

Faster Winner Determination Algorithms for (Colored) Arc Kayles

Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono, Kanae Yoshiwatari

Vol. 14519 page： 297 - 310 2024

Structural Parameterizations of Vertex Integrity

Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi

Vol. 14549 page： 406 - 420 2024

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

Hanaka Tesshu, Ono Hirotaka, Sugiyama Kosuke

International Journal of Networking and Computing Vol. 14 ( 1 ) page： 26 - 39 2024

Language：English Publisher：IJNC Editorial Committee

For an undirected graph G = (V,E) and a k-non-negative integer vector p = (p1, . . . , pk), a mapping l : V → N∪{0} is called an L(p)-labeling of G if |l(u) − l(v)| ≥ pd for any two distinct vertices u, v ∈ V with distance d, and the maximum value of {l(v) | v ∈ 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 O(2nn2) time, where n is the number of vertices, and so on.

DOI： 10.15803/ijnc.14.1_26

Maximizing utilitarian and Egalitarian welfare of fractional hedonic games on tree-like graphs

Tesshu Hanaka, Airi Ikeyama, Hirotaka Ono

Journal of Combinatorial Optimization Vol. 14461 LNCS ( 3 ) page： 392 - 405 2024

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

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

International Journal of Networking and Computing Vol. 14 ( 1 ) page： 26 - 39 2024

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

土中哲秀, 小野廣隆

Int. J. Netw. Comput. Vol. 14(1) page： 26 - 39 2024

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

Hirotaka Ono, Hisato Yamanaka

Discrete Applied Mathematics Vol. 341 page： 93 - 101 2023.12

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

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

IPDPS Workshops 2023 Vol. abs/2303.01290 2023.5

Sequentially Swapping Tokens: Further on Graph Classes.

Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science(SOFSEM) Vol. 13878 page： 222 - 235 2023

Approximation Algorithms for the Longest Run Subsequence Problem. Reviewed Open Access

小野廣隆

Leibniz International Proceedings in Informatics (LIPIcs) Vol. 259 2023

Shortest Beer Path Queries Based on Graph Decomposition. Open Access

Tesshu Hanaka, Hirotaka Ono 0001, Kunihiko Sadakane, Kosuke Sugiyama

ISAAC Vol. 283 page： 37 - 20 2023

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 page： 308 - 313 2023

Publisher：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

The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality Open Access

Approximation Algorithms for the Longest Run Subsequence Problem Reviewed International coauthorship

小野廣隆

CPM 2023 Vol. 259 2023

Shortest Beer Path Queries based on Graph Decomposition Reviewed

土中哲秀, 小野廣隆

ISAAC 2023 Vol. 283 2023

Fukuzono Naoka, Hanaka Tesshu, Kiya Hironori, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS Vol. 321 page： 281 - 294 2022.11

Language：Japanese Publisher：Discrete Applied Mathematics

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). It models the diffusion process of information in social networks where several competitive companies want to spread their information, for example. The nature of this game strongly depends on the graph topology, and the relationship is studied from several aspects. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on split graphs, block graphs, and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that a pure Nash equilibrium does not always exist on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

DOI： 10.1016/j.dam.2022.04.025

Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants Open Access

Asahiro Y., Jansson J., Lin G., Miyano E., Ono H., Utashima T.

Leibniz International Proceedings in Informatics, LIPIcs Vol. 223 2022.6

Language：Japanese Publisher：Leibniz International Proceedings in Informatics, LIPIcs

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 paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [2], the Multiset-Restricted Common Subsequence problem (MRCS) [11], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [5, 6]. 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 [2], where the two input sequences have lengths n and poly(n). 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.4230/LIPIcs.CPM.2022.15

Capacitated Network Design Games on a Generalized Fair Allocation Model

Hanaka T., Hirose T., Ono H.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas Vol. 3 page： 1616 - 1617 2022

Language：Japanese Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas

The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge costs and capacities, each agent wants to construct a path from a source to a sink with low cost. The cost of each edge is shared by the users based on a cost-sharing function. One of simple cost-sharing functions is defined as the cost divided by the number of users. It models an ideal setting, where no overhead arises when people share things, though it might be quite rare in real life. In this paper, we model more realistic scenarios of cost-sharing connection games by generalizing the cost-sharing function. The arguments do not depend on specific cost-sharing functions and are applicable for a class of all natural cost-sharing scenarios, which include equal divisions with any natural functional overheads. We show that many bounds of the Price of Anarchy and the Price of Stability under sum-cost and max-cost criteria inherit the no-overhead case.

Computing L(p, 1)-Labeling with Combined Parameters

Hanaka T., Kawai K., Ono H.

Journal of Graph Algorithms and Applications Vol. 26 ( 2 ) page： 241 - 255 2022

Language：Japanese Publisher：Journal of Graph Algorithms and Applications

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices u and v, |f(u) − f(v)| ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e.,maxu∈V (f(u)) − minu∈V (f(u)) + 1). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

DOI： 10.7155/jgaa.00592

Fair Ride Allocation on a Line

Amano Y., Igarashi A., Kawase Y., Makino K., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 13584 LNCS page： 421 - 435 2022

Language：Japanese Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This paper extends it to the so-called assignment setting, that is, for multiple facilities and agents, each agent chooses a facility to use and shares the cost with the other agents. Such a situation can be often seen in sharing economy, such as sharing fees for office desks among workers, and taxi fare among customers of possibly different destinations on a line. Our model is regarded as a coalition formation game, based on the fair cost-sharing of the airport problem; we call our model a fair ride allocation on a line. As the criteria of solution concepts, we incorporate Nash stability and envy-freeness into our setting. We show that a Nash-stable feasible allocation that minimizes the social cost of agents can be computed efficiently if a feasible allocation exists. For envy-freeness, we provide several structural properties of envy-free allocations. Based on these, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show the NP-hardness of determining the existence of an allocation under two relaxed envy-free concepts.

DOI： 10.1007/978-3-031-15714-1_24

Reallocation Problems with Minimum Completion Time.

Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

COCOON Vol. 13595 page： 292 - 304 2022

Capacitated Network Design Games on a Generalized Fair Allocation Model Reviewed

小野廣隆

Proceedings of 21st International Conference on Autonomous Agents and Multiagent Systems, {AAMAS} 2022 Vol. - page： 1616 - 1617 2022

Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants. Reviewed International coauthorship

小野廣隆

33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, LIPIcs Vol. 223 2022

Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants Reviewed International coauthorship

小野廣隆

33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) Vol. 33 2022

Capacitated Network Design Games on a Generalized Fair Allocation Model Reviewed

土中哲秀, 小野廣隆

21st International Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2022) Vol. 21 page： 1616 - 1617 2022

コンピュテーション研究会　近況報告

増澤利光, 小野廣隆, 安藤映, 大下福仁

情報・システムソサイエティ誌 Vol. 26 ( 2 ) page： 10 - 11 2021.8

Staging of astrocytopathy and complement activation in neuromyelitis optica spectrum disorders Open Access

Takai Y., Misu T., Suzuki H., Takahashi T., Okada H., Tanaka S., Okita K., Sasou S., Watanabe M., Namatame C., Matsumoto Y., Ono H., Kaneko K., Nishiyama S., Kuroda H., Nakashima I., Lassmann H., Fujihara K., Itoyama Y., Aoki M.

Brain Vol. 144 ( 8 ) page： 2401 - 2415 2021.8

Publisher：Brain

Aquaporin 4 (AQP4)-IgG-positive neuromyelitis optica spectrum disorder (AQP4-IgG+NMOSD) is an autoimmune astrocytopathic disease pathologically characterized by the massive destruction and regeneration of astrocytes with diverse types of tissue injury with or without complement deposition. However, it is unknown whether this diversity is derived from differences in pathological processes or temporal changes. Furthermore, unlike for the demyelinating lesions in multiple sclerosis, there has been no staging of astrocytopathy in AQP4-IgG+NMOSD based on astrocyte morphology. Therefore, we classified astrocytopathy of the disease by comparing the characteristic features, such as AQP4 loss, inflammatory cell infiltration, complement deposition and demyelination activity, with the clinical phase. We performed histopathological analyses in eight autopsied cases of AQP4-IgG+NMOSD. Cases comprised six females and two males, with a median age of 56.5 years (range, 46-71 years) and a median disease duration of 62.5 months (range, 0.6-252 months). Astrocytopathy in AQP4-IgG+NMOSD was classified into the following four stages defined by the astrocyte morphology and immunoreactivity for GFAP: (i) astrocyte lysis: extensive loss of astrocytes with fragmented and/or dust-like particles; (ii) progenitor recruitment: loss of astrocytes except small nucleated cells with GFAP-positive fibre-forming foot processes; (iii) protoplasmic gliosis: presence of star-shaped astrocytes with abundant GFAP-reactive cytoplasm; and (iv) fibrous gliosis: lesions composed of densely packed mature astrocytes. The astrocyte lysis and progenitor recruitment stages dominated in clinically acute cases (within 2 months after the last recurrence). Findings common to both stages were the loss of AQP4, a decreased number of oligodendrocytes, the selective loss of myelin-associated glycoprotein and active demyelination with phagocytic macrophages. The infiltration of polymorphonuclear cells and T cells (CD4-dominant) and the deposition of activated complement (C9neo), which reflects the membrane attack complex, a hallmark of acute NMOSD lesions, were selectively observed in the astrocyte lysis stage (98.4% in astrocyte lysis, 1.6% in progenitor recruitment, and 0% in protoplasmic gliosis and fibrous gliosis). Although most of the protoplasmic gliosis and fibrous gliosis lesions were accompanied by inactive demyelinated lesions with a low amount of inflammatory cell infiltration, the deposition of complement degradation product (C3d) was observed in all four stages, even in fibrous gliosis lesions, suggesting the past or chronic occurrence of complement activation, which is a useful finding to distinguish chronic lesions in NMOSD from those in multiple sclerosis. Our staging of astrocytopathy is expected to be useful for understanding the unique temporal pathology of AQP4-IgG+NMOSD.

DOI： 10.1093/brain/awab102

Hedonic seat arrangement problems Open Access

Bodlaender H.L., Hanaka T., Jaffke L., Ono H., Otachi Y., van der Zanden T.C.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas Vol. 2020-May page： 1777 - 1779 2020

Language：Japanese Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas

In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on the neighbors in the graph. In this paper, we study the price of stability and fairness in Seat Arrangement, and the computational complexity and the parameterized complexity of finding certain “good” seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement.

DOI： 10.1007/s10458-025-09711-x

Sequentially swapping tokens: Further on graph classes

Hedonic Seat Arrangement Problems Reviewed International coauthorship

小野廣隆

Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems Vol. - page： 1777 - 1779 2020

Hedonic Seat Arrangement Problems Reviewed International coauthorship

小野廣隆

Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand Vol. - page： 1777 - 1779 2020

Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

Journal of Computer and System Sciences Vol. 155 page： 103691 - 103691 2026.2

Colored Node Kayles: Algorithms and Computational Complexity

Tesshu Hanaka, Hirotaka Ono, Kanae Yoshiwatari

Vol. 16366 LNAI page： 461 - 478 2026

Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion

Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono, Alexander Wolff

Vol. 16444 LNCS page： 451 - 466 2026

Finding a HIST: Chordality, Structural Parameters, and Diameter

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono

Vol. 16448 LNCS page： 303 - 316 2026

Reallocation Problems with Minimum Completion Time

Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

Algorithmica Vol. 87 ( 9 ) page： 1311 - 1339 2025.9

Hedonic seat arrangement problems. Open Access

Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono 0001, Yota Otachi, Tom C. van der Zanden

Autonomous Agents and Multi-Agent Systems Vol. 39 ( 2 ) page： 33 - 33 2025.7

Fair Ride Allocation on a Line Open Access

Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

ACM Transactions on Economics and Computation Vol. 13 ( 1 ) 2025.3

Fair Ride Allocation on a Line Reviewed

Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

ACM Transactions on Economics and Computation 2025.2

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints. Reviewed Open Access

Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann, Yasuko Matsui, Hirotaka Ono 0001

Algorithms Vol. 18 ( 2 ) page： 112 - 112 2025.2

An improved spectral lower bound of treewidth. Reviewed

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi

Information Processing Letters Vol. 188 page： 106536 - 106536 2025.2

On the Complexity of Minimising the Moving Distance for Dispersing Objects.

Nicolás Honorato Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono 0001

CoRR Vol. abs/2502.12903 2025.2

Shortest Longest-Path Graph Orientations for Trees. Reviewed

Yuichi Asahiro, Jesper Jansson 0001, Avraham A. Melkman, Eiji Miyano, Hirotaka Ono 0001, Quan Xue, Yoshichika Yano, Shay Zakov

SOFSEM (1) Vol. 15538 page： 51 - 64 2025

On the Complexity of Minimising the Moving Distance for Dispersing Objects. Open Access

Nicolás Honorato Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono 0001

19th International Symposium on Algorithms and Data Structures(WADS) Vol. 349 page： 36 - 14 2025

Enumeration of Ordered Trees with Leaf Restrictions.

Yasuaki Kobayashi, Dominik Köppl, Yasuko Matsui, Hirotaka Ono 0001, Toshiki Saitoh, Yushi Uno

From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday page： 8 - 19 2025

Computational complexity of Turning Tiles

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

International Journal of Game Theory Vol. 53 ( 4 ) page： 1211 - 1222 2024.12

Safe sets and in-dominating sets in digraphs.

Yandong Bai, Jørgen Bang-Jensen, Shinya Fujita 0001, Hirotaka Ono 0001, Anders Yeo

Discrete Applied Mathematics Vol. 346 page： 215 - 227 2024.3

Collecting Balls on a Line by Robots with Limited Energy

HANAKA Tesshu, HONORATO DROGUETT Nicolás, KURITA Kazuhiro, ONO Hirotaka, OTACHI Yota

IEICE Transactions on Information and Systems Vol. E107.D ( 3 ) page： 325 - 327 2024.3

Language：English Publishing type：Research paper (scientific journal) Publisher：The Institute of Electronics, Information and Communication Engineers

In this paper, we study BALL COLLECTING WITH LIMITED ENERGY, which is a problem of scheduling robots with limited energy confined to a line to catch moving balls that eventually cross the line. For this problem, we show the NP-completeness of the general case and some algorithmic results for some cases with a small number of robots.

DOI： 10.1587/transinf.2023fcl0003

On a Spectral Lower Bound of Treewidth

GIMA Tatsuya, HANAKA Tesshu, NORO Kohei, ONO Hirotaka, OTACHI Yota

IEICE Transactions on Information and Systems Vol. E107.D ( 3 ) page： 328 - 330 2024.3

Language：English Publishing type：Research paper (scientific journal) Publisher：The Institute of Electronics, Information and Communication Engineers

In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

DOI： 10.1587/transinf.2023fcl0002

On the Computational Complexity of Generalized Common Shape Puzzles.

Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono 0001, Ryuhei Uehara

SOFSEM Vol. 14519 page： 55 - 68 2024

Shortest Longest-Path Graph Orientations

Yuichi Asahiro, Jesper Jansson, Avraham A. Melkman, Eiji Miyano, Hirotaka Ono, Quan Xue, Shay Zakov

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 14422 LNCS page： 141 - 154 2024

Publishing type：Research paper (international conference proceedings)

We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph G= (V, E) in which every edge { u, v} ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions (u, v) and (v, u), and asks for an orientation, i.e., an assignment of a direction to each edge of G, such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

DOI： 10.1007/978-3-031-49190-0_10

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints.

Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono 0001

IWOCA Vol. 14764 page： 232 - 246 2024

An improved spectral lower bound of treewidth.

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi

CoRR Vol. abs/2404.08520 2024

On the complexity of finding a spanning even tree in a graph.

Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Atsuki Nagao, Hirotaka Ono 0001, Kazuhisa Seto

CoRR Vol. abs/2412.17307 2024

Reconfiguration of cliques in a graph. Open Access

Takehiro Ito, Hirotaka Ono, Yota Otachi

Discret. Appl. Math. Vol. 333 page： 43 - 58 2023.7

Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

Tesshu Hanaka, Hirotaka Ono, Yota Otachi, Saeki Uda

Lecture Notes in Computer Science Vol. 13898 page： 263 - 277 2023.4

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

Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki

CoRR Vol. abs/2312.10599 2023

On the Computational Complexity of Generalized Common Shape Puzzles.

Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono, Ryuhei Uehara

CoRR Vol. abs/2305.10749 2023

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.

Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono

CoRR Vol. abs/2308.16426 2023

Approximation Algorithms for the Longest Run Subsequence Problem. Open Access

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson 0001, Guohui Lin, Eiji Miyano, Hirotaka Ono, Shunichi Tanaka

CPM Vol. 259 page： 2 - 12 2023

Shortest Beer Path Queries based on Graph Decomposition.

Tesshu Hanaka, Hirotaka Ono 0001, Kunihiko Sadakane, Kosuke Sugiyama

CoRR Vol. abs/2307.02787 2023

Turning Tiles is PSPACE-complete.

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

CoRR Vol. abs/2310.01983 2023

Parameterized Complexity of (A, ℓ )-Path Packing. Reviewed Open Access

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono, Yota Otachi

Algorithmica Vol. 84 ( 4 ) page： 871 - 895 2022.4

Upper and lower degree-constrained graph orientation with minimum penalty. Reviewed Open Access

Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono

Theor. Comput. Sci. Vol. 900 page： 53 - 78 2022.1

Modeling Imperfect Information TANHINMIN with Structural Oracle Reviewed Open Access

Hironori Kiya, Katsuki Ohto, Hirotaka Ono

IPSJ Transactions on Mathematical Modeling and Its Applications Vol. 15 ( 1 ) page： 10 - 17 2022.1

Winner Determination Algorithms for Graph Games with Matching Structures.

Kanae Yoshiwatari, Hironori Kiya, Tesshu Hanaka, Hirotaka Ono

IWOCA Vol. 13270 LNCS page： 509 - 522 2022

Capacitated Network Design Games on a Generalized Fair Allocation Model.

Tesshu Hanaka, Toshiyuki Hirose, Hirotaka Ono

21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS) page： 1616 - 1617 2022

Winner Determination Algorithms for Graph Games with Matching Structures.

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

CoRR Vol. abs/2211.05307 2022

Sequentially Swapping Tokens: Further on Graph Classes.

Hironori Kiya, Yuto Okada, Hirotaka Ono 0001, Yota Otachi

CoRR Vol. abs/2210.02835 2022

Algorithmic Approach for Combinatorial Game Theory Open Access

Kiya Hironori, Ono Hirotaka

SYSTEMS, CONTROL AND INFORMATION Vol. 65 ( 10 ) page： 415 - 420 2021.10

Computing the Winner of 2-Player TANHINMIN

KIYA Hironori, OHTO Katsuki, ONO Hirotaka

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol. E104.A ( 9 ) page： 1134 - 1141 2021.9

Authorship：Last author Language：English Publishing type：Research paper (scientific journal) Publisher：The Institute of Electronics, Information and Communication Engineers

DAIHINMIN, which means Grand Pauper, is a popular playing-card game in Japan. TANHINMIN is a simplified variant of DAIHINMIN, which was proposed by Nishino in 2007 in order to investigate the mathematical properties of DAIHINMIN. In this paper, we consider a 2-player generalized TANHINMIN, where the deck size is arbitrary n. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.

DOI： 10.1587/transfun.2020dmp0026

Graph Orientation with Edge Modifications Reviewed International coauthorship Open Access

Asahiro, Y., Jansson, J., Miyano, E., Ono, H., S, hya, T.P.

International Journal of Foundations of Computer Science Vol. 32 ( 02 ) page： 209 - 233 2021.2

Language：Japanese Publishing type：Research paper (scientific journal) Publisher：World Scientific Pub Co Pte Lt

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph [Formula: see text] of an input undirected graph [Formula: see text] such that either: (Type I) the number of edges in [Formula: see text] is minimized or maximized and [Formula: see text] can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of [Formula: see text] that can be constructed by deleting or inserting a fixed number of edges, [Formula: see text] admits an orientation optimizing some objective involving the vertices’ outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) [Formula: see text]-DEL-MAX, [Formula: see text]-INS-MIN, [Formula: see text]-INS-MAX, and [Formula: see text]-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

DOI： 10.1142/S012905412150012X

Reallocation Problems with Minimum Completion Time.

Computing L(p, 1)-Labeling with Combined Parameters Reviewed

Tesshu Hanaka, Kazuma Kawai, Hirotaka Ono

WALCOM: Algorithms and Computation Vol. 12635 LNCS page： 208 - 220 2021.2

Fairness norm through social networks: a simulation approach Open Access

Rifki, O., Ono, H.

Computational Social Networks Vol. 8 ( 1 ) 2021

Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

CoRR Vol. abs/2111.02579 2021

Graph orientation with splits Reviewed International coauthorship Open Access

Asahiro, Y., Jansson, J., Miyano, E., Nikpey, H., Ono, H.

Theoretical Computer Science Vol. 844 page： 16 - 25 2020.12

Exact algorithms for the repetition-bounded longest common subsequence problem Reviewed International coauthorship Open Access

Asahiro, Y., Jansson, J., Lin, G., Miyano, E., Ono, H., Utashima, T.

Theoretical Computer Science Vol. 838 page： 238 - 249 2020.10

Parameterized complexity of independent set reconfiguration problems Reviewed International coauthorship Open Access

Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

Discrete Applied Mathematics Vol. 283 page： 336 - 345 2020.9

Independent Set Reconfiguration Parameterized by Modular-Width Reviewed Open Access

Belmonte, R., Hanaka, T., Lampis, M., Ono, H., Otachi, Y.

Algorithmica Vol. 82 ( 9 ) page： 2586 - 2605 2020.9

Parameterized Complexity of $$(A,\ell )$$-Path Packing Reviewed International coauthorship Open Access

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

Lecture Notes in Computer Science Vol. 12126 LNCS page： 43 - 55 2020.6

Parameterized Complexity of Safe Set Reviewed International coauthorship

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

Journal of Graph Algorithms and Applications Vol. 24 ( 3 ) page： 215 - 245 2020.4

Space-Efficient Algorithms for Longest Increasing Subsequence Reviewed International coauthorship Open Access

Kiyomi, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J.

Theory of Computing Systems Vol. 64 ( 3 ) page： 522 - 541 2020.4

Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium Reviewed

Naoka Fukuzono, Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Ryogo Yamaguchi

SOFSEM 2020: Theory and Practice of Computer Science Vol. 12011 page： 627 - 635 2020

The computational complexity of the gear placement problem Open Access

HAMA Vitor Mitsuo FUKUSHIGUE, KANAZAWA Shogo, HU Yannan, IMAHORI Shinji, ONO Hirotaka, YAGIURA Mutsunori

Journal of Advanced Mechanical Design, Systems, and Manufacturing Vol. 14 ( 5 ) page： JAMDSM0069 - JAMDSM0069 2020

Language：English Publishing type：Research paper (scientific journal) Publisher：The Japan Society of Mechanical Engineers

In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed. The task is to find a placement of a set of gears called sub-gears, to connect every target gear to the torque generator source so that every target gear rotates in a given direction. The objective is to minimize the number of sub-gears to be used. We prove that the GPP is NP-hard by giving a reduction from the Hamiltonian path problem on 3-regular planar graphs, which is known to be NP-complete, to the GPP. We also present an upper bound for the number of sub-gears to be placed.

DOI： 10.1299/jamdsm.2020jamdsm0069

Hedonic Seat Arrangement Problems. Reviewed International journal

Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems page： 1777 - 1779 2020

Fair Ride Allocation on a Line.

Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

CoRR Vol. abs/2007.08045 2020

A faster parameterized algorithm for PSEUDOFOREST DELETION Reviewed Open Access

Bodlaender Hans L., Ono Hirotaka, Otachi Yota

DISCRETE APPLIED MATHEMATICS Vol. 236 page： 42-56 2018.2

Finding environmentally critical transmission sectors, transactions, and paths in global supply chain networks Reviewed

Hanaka Tesshu, Kagawa Shigemi, Ono Hirotaka, Kanemoto Keiichiro

ENERGY ECONOMICS Vol. 68 page： 44-52 2017.10

Combinatorial Structure Extraction from Large-Scale Data by String Compression

page： 1-8 2017

Subexponential fixed-parameter algorithms for partial vector domination Reviewed Open Access

Ishii Toshimasa, Ono Hirotaka, Uno Yushi

DISCRETE OPTIMIZATION Vol. 22 page： 111-121 2016.11

The complexity of dominating set reconfiguration Reviewed Open Access

Haddadan Arash, Ito Takehiro, Mouawad Amer E., Nishimura Naomi, Ono Hirotaka, Suzuki Akira, Tebbal Youcef

THEORETICAL COMPUTER SCIENCE Vol. 651 page： 37-49 2016.10

On the Maximum Weight Minimal Separator (コンピュテーション)

土中哲秀, Bodlaender Hans L., Zanden T. C. van der, 小野廣隆

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 Vol. 116 ( 116 ) page： 81-87 2016.6

情報の窓 2015年秋季シンポジウムルポ(第74回)

小野廣隆

オペレーションズ・リサーチ Vol. 61 ( 2 ) page： 109-111 2016.2

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

THEORY OF COMPUTING SYSTEMS Vol. 58 ( 1 ) page： 60-93 2016.1

Linear-time algorithm for sliding tokens on trees Reviewed Open Access

Demaine Erik D., Demaine Martin L., Fox-Epstein Eli, Hoang Duc A., Ito Takehiro, Ono Hirotaka, Otachic Yota, Uehara Ryuhei, Yamada Takeshi

THEORETICAL COMPUTER SCIENCE Vol. 600 page： 132-142 2015.10

2-H-2 IFRS導入の影響に関するCFOアンケート結果からの安定クラスタ抽出(経営)

大迫俊輔, 小野廣隆, 小津稚加子

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2015 page： 252-253 2015.9

1-G-3 産業連関ネットワーク解析のための疎化処理と閾値の関係について(公共)

土中哲秀, 小野廣隆

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2015 page： 130-131 2015.9

Approximability of minimum certificate dispersal with tree structures Reviewed Open Access

Izumi Taisuke, Izumi Tomoko, Ono Hirotaka, Wada Koichi

THEORETICAL COMPUTER SCIENCE Vol. 591 page： 5-14 2015.8

The searchlight problem for road networks Reviewed Open Access

Dereniowski Dariusz, Ono Hirotaka, Suzuki Ichiro, Wrona Lukasz, Yamashita Masafumi, Zylinski Pawel

THEORETICAL COMPUTER SCIENCE Vol. 591 page： 28-59 2015.8

On the approximability and hardness of minimum topic connected overlay and its special instances (vol 429, pg 144, 2012) Reviewed Open Access

Hosoda Jun, Hromkovic Juraj, Izumi Taisuke, Ono Hirotaka, Steinova Monika, Wada Koichi

THEORETICAL COMPUTER SCIENCE Vol. 562 page： 660-661 2015.1

PATTERN FORMATION BY OBLIVIOUS ASYNCHRONOUS MOBILE ROBOTS Reviewed

Fujinaga Nao, Yamauchi Yukiko, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

SIAM JOURNAL ON COMPUTING Vol. 44 ( 3 ) page： 740-785 2015

Subgraph Domatic Problem and Writing Capacity of Memory Devices with Restricted State Transitions Reviewed

Wadayama Tadashi, Izumi Taisuke, Ono Hirotaka

2015 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) page： 1307-1311 2015

Finding All Longest Common Segments in Protein Structures Efficiently Reviewed

Ng Yen Kaow, Yin Linzhi, Ono Hirotaka, Li Shuai Cheng

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS Vol. 12 ( 3 ) page： 644-655 2015

Reconfiguration of Cliques in a Graph Reviewed

Ito Takehiro, Ono Hirotaka, Otachi Yota

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015) Vol. 9076 page： 212-223 2015

次数制約のあるグラフ有向化問題の計算複雑さについて (回路とシステム)

朝廣雄一, ジャンソンジェスパー, 宮野英次, 小野廣隆

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 Vol. 114 ( 312 ) page： 105-112 2014.11

Language：Japanese Publishing type：Research paper (scientific journal)

無向グラフに対するオリエンテーション(グラフ有向化)とは,各辺に対して向き付けを行うことである.オリエンテーションによる結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に,それを次数制約オリエンテーションと呼ぶ.本稿では,次数制約オリエンテーションを求める問題の一種である,2つのお互いに関連するMIN W-LIGHT問題とMAX W-HEAVY問題について考える.任意の固定された非負整数Wに対して,MIN W-LIGHT(またはMAX W-HEAVY)問題は,入力された無向グラフGのオリエンテーションのうち,出次数W以下(またはWP以上)の頂点数を最小化(または最大化)するものを発見することを目的とする.これらの問題の計算複雑さはWの値によって変化する.本稿では,これらの問題の計算複雑さ(主に近似可能性)に関するいくつかの結果を示す.

次数制約のあるグラフ有向化問題の計算複雑さについて (システム数理と応用)

朝廣雄一, ジャンソンジェスパー, 宮野英次, 小野廣隆

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 Vol. 114 ( 313 ) page： 105-112 2014.11

Language：Japanese Publishing type：Research paper (scientific journal)

次数制約のあるグラフ有向化問題の計算複雑さについて

朝廣雄一, ジャンソンジェスパー, 宮野英次, 小野廣隆

研究報告アルゴリズム（AL） Vol. 2014 ( 19 ) page： 1-8 2014.11

Language：Japanese Publishing type：Research paper (scientific journal)

無向グラフに対するオリエンテーション（グラフ有向化）とは，各辺に対して向き付けを行うことである．オリエンテーションによる結果として得られる有向グラフにおいて，各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に，それを次数制約オリエンテーションと呼ぶ．本稿では，次数制約オリエンテーションを求める問題の一種である，2 つのお互いに関連する Min W-Light 問題と Max W-Heavy 問題について考える．任意の固定された非負整数 W に対して，Min W-Light （または Max W-Heavy）問題は，入力された無向グラフ G のオリエンテーションのうち，出次数 W 以下（または W 以上）の頂点数を最小化（または最大化）するものを発見することを目的とする．これらの問題の計算複雑さは W の値によって変化する．本稿では，これらの問題の計算複雑さ（主に近似可能性）に関するいくつかの結果を示す．

2-C-3 最大辺支配問題に対する固定パラメータアルゴリズム(離散最適化(4))

Base-object location problems for base-monotone regions Reviewed Open Access

Chun Jinhee, Horiyama Takashi, Ito Takehiro, Kaothanthong Natsuda, Ono Hirotaka, Otachi Yota, Tokuyama Takeshi, Uehara Ryuhei, Uno Takeaki

THEORETICAL COMPUTER SCIENCE Vol. 555 page： 71-84 2014.10

土中哲秀, 小野廣隆

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2014 page： 198-199 2014.8

1-H-10 IFRS導入の影響に関するCFOアンケートの因子分析(OR一般)

大迫俊輔, 小野廣隆, 小津稚加子

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2014 page： 158-159 2014.8

Reconfiguration of list L(2,1)-labelings in a graph Reviewed Open Access

Ito Takehiro, Kawamura Kazuto, Ono Hirotaka, Zhou Xiao

THEORETICAL COMPUTER SCIENCE Vol. 544 page： 84-97 2014.8

Approximating the path-distance-width for AT-free graphs and graphs in related classes Reviewed Open Access

Otachi Yota, Saitoh Toshiki, Yamanaka Katsuhisa, Kijima Shuji, Okamoto Yoshio, Ono Hirotaka, Uno Yushi, Yamazaki Koichi

DISCRETE APPLIED MATHEMATICS Vol. 168 page： 69-77 2014.5

Robustness Analysis of Evolutionary Algorithms to Portfolio Optimization Against Errors in Asset Means Reviewed

Rifki Omar, Ono Hirotaka

OPERATIONS RESEARCH PROCEEDINGS 2013 page： 369-375 2014

Depth-First Search Using O(n) Bits Reviewed

Asano Tetsuo, Izumi Taisuke, Kiyomi Masashi, Konagaya Matsuo, Ono Hirotaka, Otachi Yota, Schweitzer Pascal, Tarui Jun, Uehara Ryuhei

ALGORITHMS AND COMPUTATION, ISAAC 2014 Vol. 8889 page： 553-564 2014

(Total) Vector Domination for Graphs with Bounded Branchwidth Reviewed

Ishii Toshimasa, Ono Hirotaka, Uno Yushi

LATIN 2014: THEORETICAL INFORMATICS Vol. 8392 page： 238-249 2014

Fixed-Parameter Tractability of Token Jumping on Planar Graphs Reviewed

Ito Takehiro, Kaminski Marcin, Ono Hirotaka

ALGORITHMS AND COMPUTATION, ISAAC 2014 Vol. 8889 page： 208-219 2014

Polynomial-Time Algorithm for Sliding Tokens on Trees Reviewed

Demaine Erik D., Demaine Martin L., Fox-Epstein Eli, Hoang Duc A., Ito Takehiro, Ono Hirotaka, Otachi Yota, Uehara Ryuhei, Yamada Takeshi

ALGORITHMS AND COMPUTATION, ISAAC 2014 Vol. 8889 page： 389-400 2014

Approximability of Latin Square Completion-Type Puzzles Reviewed

Haraguchi Kazuya, Ono Hirotaka

FUN WITH ALGORITHMS Vol. 8496 page： 218-229 2014

On the Parameterized Complexity for Token Jumping on Graphs Reviewed

Ito Takehiro, Kaminski Marcin, Ono Hirotaka, Suzuki Akira, Uehara Ryuhei, Yamanaka Katsuhisa

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014) Vol. 8402 page： 341-351 2014

Approximability of graph orientation problems with degree constraints

ASAHIRO Yuichi, JANSSON Jesper, MIYANO Eiji, ONO Hirotaka

IEICE technical report. Theoretical foundations of Computing Vol. 113 ( 371 ) page： 123-130 2013.12

Language：Japanese Publishing type：Research paper (scientific journal)

A degree-constrained graph orientation of an undirected graph is an assignment of a direction to each edge in the graph such that the outdegree of every vertex in the resulting directed graph satisfies a prescribed lower and/or upper bound. Such graph orientations have been studied in many literatures and various characterizations are known. We consider two related optimization problems introduced in [3]: For any fixed non-negative integer W, the problem MAX W-LIGHT (or MIN W-HEAVY) takes as input an undirected graph G and ask for an orientation of G that maximizes (or minimizes) the number of vertices with outdegree at most W (or at least W). The problems' computational complexities vary with W. In this paper we show several results related to their polynomial-time approximability.

グラフの独立点集合遷移問題に対するアルゴリズム

Demaine Erik D., Demaine Martin L., 伊藤健洋, 小野廣隆, 上原隆平

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 Vol. 113 ( 371 ) page： 7-14 2013.12

Language：English Publishing type：Research paper (scientific journal)

グラフGに対し,|I_b|=|I_r|であるような2つの独立点集合I_bとI_rが与えられたとする.また,Gにおいて,I_bに含まれる各点にはトークンが置かれているとする.スライディングトークン問題とは,I_bからI_rへのGの独立点集合の系列が存在するか判定する問題である.ただし,系列に含まれる各独立点集合は,その1つ前の独立点集合から,ただ1つのトークンをGの辺に沿ってスライドさせることで得られなければならない.この問題は,理想グラフに対してPSPACE完全であることが知られている.本論文では,理想グラフのいくつかの部分クラスに対して,この問題がO(n)時間で解けることを示す.ここで,nはグラフの点数である.また,これらのグラフに対しては,実際にI_bからI_rへ遷移させる最短の系列を多項式時間で見つけることができる.

太陽熱と非常時対応可能なコージェネレーションによる熱利用システムの導入事例 : 尼崎D.C.グランスクエア (特集集合住宅の省エネルギー) -- (集合住宅における省エネへの取組み)

Optimal approximability of bookmark assignments Reviewed Open Access

Asahiro Yuichi, Miyano Eiji, Murata Toshihide, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS Vol. 161 ( 16-17 ) page： 2361-2366 2013.11

A Linear Time Algorithm for L(2,1)-Labeling of Trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMICA Vol. 66 ( 3 ) page： 654-681 2013.7

BLOCKSUM is NP-Complete Reviewed Open Access

Haraguchi Kazuya, Ono Hirotaka

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS Vol. E96D ( 3 ) page： 481-488 2013.3

Route-Enabling Graph Orientation Problems Reviewed

Ito Takehiro, Miyamoto Yuichiro, Ono Hirotaka, Tamaki Hisao, Uehara Ryuhei

ALGORITHMICA Vol. 65 ( 2 ) page： 317-338 2013.2

府川一郎, 中條広隆, 小野建

IBEC Vol. 33 ( 5 ) page： 40-43 2013.1

Measuring Sensitivity of Evolutionary Algorithms to Errors in Asset Means for Mean-Variance Portfolio Optimization. Open Access

Rifki Omar

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2013 ( 0 ) page： 181-182 2013

COALESCING RANDOM WALKS AND VOTING ON CONNECTED GRAPHS Reviewed Open Access

Cooper Colin, Elsaesser Robert, Ono Hirotaka, Radzik Tomasz

SIAM JOURNAL ON DISCRETE MATHEMATICS Vol. 27 ( 4 ) page： 1748-1758 2013

On space complexity of self-stabilizing leader election in mediated population protocol Reviewed

Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

DISTRIBUTED COMPUTING Vol. 25 ( 6 ) page： 451-460 2012.12

RA-002 Detecting Network Security Incidents Based on String Compression Open Access

Eto Kouki, Ono Hirotaka, Yamashita Masafumi, Takeuchi Jun'ichi

Vol. 11 ( 1 ) page： 9-16 2012.9

Deductive Inference for the Interiors and Exteriors of Horn Theories Reviewed

Makino Kazuhisa, Ono Hirotaka

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC Vol. 13 ( 3 ) 2012.8

ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開) Open Access

穂坂祐輔, 山内由紀子, 来嶋秀治, 小野廣隆, 山下雅史

数理解析研究所講究録 Vol. 1799 page： 130-136 2012.6

On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集) Open Access

堀山貴史, 伊藤健洋, 小野廣隆, 大舘陽太, 上原隆平, 宇野毅明

数理解析研究所講究録 Vol. 1799 page： 123-129 2012.6

The (p, q)-total labeling problem for trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

DISCRETE MATHEMATICS Vol. 312 ( 8 ) page： 1407-1420 2012.4

基単調図形に分割可能な最大重み領域を得る基線の配置問題

堀山貴史, 伊藤健洋, ガオタントンナスダ, 小野廣隆, 大舘陽太, 徳山豪, 上原隆平, 宇野毅明

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 112 ( 21 ) page： 37-43 2012.4

Language：English Publishing type：Research paper (scientific journal)

本論文では,ピクセルグリッドから最大重み領域を切り出す問題を扱う.ただし,切り出された領域は,基線に対して基単調図形に分割できなければならない.n×nピクセルグリッドと基線が与えられたとき,この問題はO(n^3)時間で解けることが知られている.これに対し本論文では,ピクセルグリッドのみが与えられたとき,k本の基線を最適に配置することはNP困難であることを示す.さらに,この配置問題に対し,O(n^3)時間の2倍近似アルゴリズムを与える。また,多項式時間で求解できるいくつかのケースや問題の変種も示す.

On the approximability and hardness of minimum topic connected overlay and its special instances Reviewed Open Access

Hosoda Jun, Hromkovic Juraj, Izumi Taisuke, Ono Hirotaka, Steinova Monika, Wada Koichi

THEORETICAL COMPUTER SCIENCE Vol. 429 page： 144-154 2012.4

木ネットワークにおける証明書分散問題の近似可能性について Open Access

泉泰介, 泉朋子, 小野廣隆, 和田幸一

第74回全国大会講演論文集 Vol. 2012 ( 1 ) page： 269-270 2012.3

Language：English Publishing type：Research paper (scientific journal)

証明書分散問題は，与えられた通信要求をセキュアに実現するために各計算機が保有しなければいけない証明書の枚数を最小化する組み合わせ最適化問題である．本研究では，通信要求グラフ，および証明書グラフが木の場合における証明書分散問題の計算困難性について論じる．通信要求グラフが木の場合，その最大次数によって計算困難さが変化すること，および証明書グラフが木の場合は多項式時間で最適解を求めることが可能であることを示す．

On the complexity of minimum topic-connected overlay problems

和田幸一 , JurajHromkovic , 泉泰介 , 小野廣隆 , SteinovaMonika

全国大会講演論文集 Vol. 2012 ( 1 ) page： 267-269 2012.3

Language：English Publishing type：Research paper (scientific journal)

In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem(Min-TCO, for short) has been investigated:Given a set of t topics and a collection of n users together with the lists of topics they are intersted in, the aim is to collect these users to a network by a minimum number of edges such that every graph induced by users intersted in a common topic is connected.In this paper, we consider the complexity of Min-TCO.

木ネットワークにおける証明書分散問題の近似可能性について Open Access

泉泰介 , 泉朋子 , 小野廣隆 , 和田幸一

全国大会講演論文集 Vol. 2012 ( 1 ) page： 269-271 2012.3

Language：English Publishing type：Research paper (scientific journal)

証明書分散問題は,与えられた通信要求をセキュアに実現するために各計算機が保有しなければいけない証明書の枚数を最小化する組み合わせ最適化問題である.本研究では,通信要求グラフ,および証明書グラフが木の場合における証明書分散問題の計算困難性について論じる.通信要求グラフが木の場合,その最大次数によって計算困難さが変化すること,および証明書グラフが木の場合は多項式時間で最適解を求めることが可能であることを示す.

On the complexity of minimum topic-connected overlay problems

和田幸一, JurajHromkovic, 泉泰介, 小野廣隆, SteinovaMonika

第74回全国大会講演論文集 Vol. 2012 ( 1 ) page： 267-268 2012.3

Language：English Publishing type：Research paper (scientific journal)

On cover time bounds of multiplex random walks

Vol. 2012 ( 9 ) page： 1-7 2012.1

An Extension of Matthews' Bound to Multiplex Random Walks Reviewed

Hosaka Yusuke, Yamauchi Yukiko, Kijima Shuji, Ono Hirotaka, Yamashita Masafumi

2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW) page： 872-877 2012

次数上下界制約付きグラフ向き付けにおけるペナルティ最小化

朝廣雄一, JANSSON Jesper, 宮野英次, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 111 ( 360 ) page： 37-44 2011.12

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei

JOURNAL OF COMBINATORIAL OPTIMIZATION Vol. 22 ( 1 ) page： 78-96 2011.7

非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用) Open Access

藤永直, 小野廣隆, 来嶋秀治, 山下雅史

数理解析研究所講究録 Vol. 1744 page： 197-200 2011.6

Approximating the path-distance-width for κ-cocompmability graphs (計算機科学とアルゴリズムの数理的基礎とその応用--RIMS研究集会報告集) Open Access

大舘陽太, 斎藤寿樹, 山中克久, 来嶋秀治, 岡本吉央, 小野廣隆, 宇野裕之, 山崎浩一

数理解析研究所講究録 Vol. 1744 page： 60-66 2011.6

マッチングを用いたパターン形成アルゴリズム

藤永直, 小野廣隆, 来嶋秀治, 山下雅史

研究報告アルゴリズム（AL） Vol. 2011 ( 4 ) page： 1-6 2011.5

Language：English Publishing type：Research paper (scientific journal)

本論文では，パターン形成問題と呼ばれる，非同期的に動くロボット群を幾何的な配置に並ばせる問題を考察する．ここでは，各ロボットは各自固有の座標系に従って，他のロボットの配置と目的の配置を観測するできるものとする．n 点の座標からなる集合の対 A,B の間のマッチングを求めるアルゴリズム "clockwise matching" を構成し，"clockwise matching" によって任意のパターン形成問題を解くことができることを示す．A geometric pattern formation problem by autonomous mobile robots is investigated in this paper. In the "embedded pattern formation problem" disscussed in this paper, the target pattern is assumed to be visible from the robots via their own (local) coordinate system. We show that our matching algorithm "clockwise matching" which calculates the matching between a pair of patterns A and B both comprising of n coordinates, solves any embedded pattern formation problem.

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Asahiro Yuichi, Miyano Eiji, Ono Hirotaka, 小野廣隆

Discrete Applied Mathematics Vol. 159 ( 7 ) page： 498-508 2011.4

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree Reviewed

Asahiro Yuichi, Miyano Eiji, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS Vol. 159 ( 7 ) page： 498-508 2011.4

GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE Vol. 22 ( 3 ) page： 583-601 2011.4

DS-1-6 On Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol

Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

Proceedings of the IEICE General Conference Vol. 2011 ( 1 ) page： "S-11"-"S-12" 2011.2

Broadcastings and digit tilings on three-dimensional torus networks Reviewed Open Access

Okazaki Ryotaro, Ono Hirotaka, Sadahiro Taizo, Yamashita Masafumi

THEORETICAL COMPUTER SCIENCE Vol. 412 ( 4-5 ) page： 307-319 2011.2

Design of Faster Random Walks by Using Topological Information of Graphs

page： 1-5 2011

The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Delta+2 Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

COMBINATORIAL ALGORITHMS Vol. 6460 page： 103-+ 2011

On the Approximability of Minimum Topic Connected Overlay and Its Special Instances Reviewed

Hosoda Jun, Hromkovic Juraj, Izumi Taisuke, Ono Hirotaka, Steinova Monika, Wada Koichi

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011 Vol. 6907 page： 376-387 2011

Approximability of the Path-Distance-Width for AT-free Graphs Reviewed

Otachi Yota, Saitoh Toshiki, Yamanaka Katsuhisa, Kijima Shuji, Okamoto Yoshio, Ono Hirotaka, Uno Yushi, Yamazaki Koichi

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE Vol. 6986 page： 271-+ 2011

最大支配問題

宮野英次, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 110 ( 325 ) page： 53-60 2010.11

Language：English Publishing type：Research paper (scientific journal)

グラフにおける頂点/辺支配集合問題の新しい亜種について考える.ある頂点はその頂点自身と隣接点を支配すると言い,同様にある辺はその辺自身と隣接する辺を支配すると言う.グラフG=(V,E)と正整数kが与えられたとき,k-頂点(k-辺)支配問題(それぞれ以下k-MaxVD, k-MaxEDと呼ぶ)は高々サイズkの頂点の部分集合D_V&subE;V(D_E&subE;E)の中で,支配する頂点集合(また辺集合)のサイズを最大化するものを求める問題である.本論文では,まずこの問題に対して単純な貪欲アルゴリズムがk-MaxVD, k-MaxEDいずれに対しても近似比(1-1/e)を達成することを示す.次にP≠NPの条件下で,k-MaxVEに対してこの近似比が多項式時間アルゴリズムの最善であることを示す.さらにP≠NPの条件下で,k-MaxEDに対して1303/1304よりも良い近似比の多項式時間アルゴリズムが存在しないことを示す.一方,kがグラフの最小最大マッチングのサイズを超えないという条件下では,k-MaxEDに対して近似比3/4の多項式時間アルゴリズムが存在することを示す.

自己安定リーダー選挙MPPにおける領域複雑度の上下界について

溝口隆, 小野廣隆, 来嶋秀治, 山下雅史

研究報告アルゴリズム（AL） Vol. 2010 ( 4 ) page： 1-5 2010.11

Language：English Publishing type：Research paper (scientific journal)

本論文は，自己安定リーダー選挙メディエイテッドポピュレーションプロトコル (SS-LE MPP) の領域複雑度に関する研究結果である．Cai，Izumi and Wada (2009) は n エージェントに対する自己安定リーダー選挙ポピュレーションプロトコル (SS-LE PP) は少なくとも n 個のエージェント状態を必要とすることを示した．さらに n エージェントに対する SS-LE MPP のうちエージェント状態数が n であるプロトコルを与えた．MPP は Chatzigiannakis，Michail and Spirakis (2009) によって紹介された．MPP は分散ネットワークモデルの 1 つで，各エージェント間に局所的なメモリを追加した PP の拡張モデルである．一般的に MPP は PP よりも計算能力が高いことが知られている．一方で SS-LE のエージェント状態に対する空間複雑度の減少可能性については知られていない．本稿では，n エージェントの SS-LE MPP のうちエージェント状態数が n-1 であり，各エージェント間に 1 ビットのメモリが与えられたプロトコルを与える．This paper investigates the space complexity of a self stabilizing leader election in a mediated population protocol (SS-LE MPP). Cai, Izumi and Wada (2009) showed that SS-LE in a population protocol (SS-LE PP) for n agents requires at least n agent-states, and gave a SS-LE PP with n agent-states for n agents. MPP is a model of distributed computation, introduced by Chatzigiannakis, Michail and Spirakis (2009) as an extension of PP allowing an extra memory on every agents pair. While they showed that MPP is stronger than PP in general, it was not known if a MPP can really reduce the space complexity of SS-LE with respect to agent-states. We in this paper give a SS-LE MPP with n - 1 agent-states and a single bit memory on every agents pair for n agents.

木の(p, q)-全ラベリング問題

蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之

研究報告アルゴリズム（AL） Vol. 2010 ( 2 ) page： 1-8 2010.11

Language：English Publishing type：Research paper (scientific journal)

グラフ G の k-(p,q)-全ラベリングとは，G の節点と辺への 0 から k までの整数値の割当てであり，節点とそれに接続する辺の間では少なくとも p，隣接する 2 節点間または 2 辺間では少なくとも q の差があるもののことをいう．G の (p, q)-全ラベリング数 λTp;q(G) は，k がとりうる値の最小値として定義される．G の (p, q)-全ラベリング問題とは，ラベリング数 λTp;q(G) を求める問題である．本研究では，いくつかのグラフクラスのグラフの (p, q)-全ラベリング数に対して新しい上界と下界を与える．とくに，グラフが木の場合にはタイトな上界と下界を与える．また，グラフが木で p≦3q/2 の場合に (p, q)-全ラベリング問題を解く線形時間アルゴリズムを与え，さらに最大次数が 4 以上という仮定が加わった場合，λTp;q(T) を実現する木Tを完全に特徴づけられることも示す．この結果は，(p; q)-全ラベリング問題の一般化である L (p; q)-ラベリング問題が q が p の約数でないすべての (p; q) の組に対し NP 困難であることと対照的である．A (p,q)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set of nonnegative integers such that |f(x)-f(y)| ≧ p if x is a vertex and y is an edge incident to x, and |f(x)-f(y)| ≧ q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) ∪ E(G). A k-(p,q)-total labeling is a (p,q)-total labeling f:V(G) ∪ E(G) → {0,...,k}, and the (p,q)-total labeling problem asks the minimum k, which we denote by λTp,q(G), among all possible assignments. In this paper, we first give new upper and lower bounds on λTp,q(G) for some classes of graphs G, in particular, tight bounds on λTp,q(T) for trees T. We then show that if p ≦ 3q/2, the problem for trees T is linearly solvable, and give a complete characterization of trees achieving λTp,q(T) if in addition Δ ≧ 4 holds, where Δ is the maximum degree of T. It is contrasting to the fact that the L(p,q)-labeling problem, which is a generalization of the (p,q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p.

A Compression Method of Suffix Arrays with Fast Decoding

A-028 Convergence of Approximately Nash Transition in Some Incomplete Congestion Games Open Access

Yamada Yosuke, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

Vol. 9 ( 1 ) page： 231-232 2010.8

A-022 Approximate String Matching using Suffix Array Compressed Open Access

Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Vol. 9 ( 1 ) page： 205-206 2010.8

A-023 Compressing a Suffix Tree by Converting it to a Binary Tree and Using Succinct Data Structures Open Access

Baba Masahiro, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Vol. 9 ( 1 ) page： 207-208 2010.8

TANAKA Yosuke, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

The IEICE transactions on information and systems Vol. 93 ( 8 ) page： 1567-1575 2010.8

Local move connectedness of domino tilings with diagonal impurities Reviewed

Nakano Fuminiko, Ono Hirotaka, Sadahiro Taizo

DISCRETE MATHEMATICS Vol. 310 ( 13-14 ) page： 1918-1931 2010.7

Approximability and inapproximability of the minimum certificate dispersal problem Reviewed

Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

THEORETICAL COMPUTER SCIENCE Vol. 411 ( 31-33 ) page： 2773-2783 2010.6

全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用) Open Access

馬場雅大, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1691 page： 155-161 2010.6

Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用) Open Access

穂坂祐輔, 小野廣隆, 山下雅史

数理解析研究所講究録 Vol. 1691 page： 85-90 2010.6

任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用) Open Access

野中良哲, 小野廣隆, 山下雅史

数理解析研究所講究録 Vol. 1691 page： 91-95 2010.6

不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用) Open Access

山田陽介, 小野廣隆, 山下雅史

数理解析研究所講究録 Vol. 1691 page： 148-154 2010.6

THE SPACE COMPLEXITY OF LEADER ELECTION IN ANONYMOUS NETWORKS Reviewed

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE Vol. 21 ( 3 ) page： 427-440 2010.6

The hitting and cover times of Metropolis walks

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi, 小野廣隆

Theoretical Computer Science Vol. 411 ( 16 ) page： 1889-1894 2010.3

The hitting and cover times of Metropolis walks Reviewed

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

THEORETICAL COMPUTER SCIENCE Vol. 411 ( 16-18 ) page： 1889-1894 2010.3

A succinct representation of a full binary tree

BABA MASAHIRO, ONO HIROTAKA, SADAKANE KUNIHIKO, YAMASHITA MASAFUMI

Vol. 2010 ( 1 ) page： 1-8 2010.2

Index with fast searching in case phrase is frequent

TANAKA YOSUKE, ONO HIROTAKA, SADAKANE KUNIHIKO, YAMASHITA MASAFUMI

Vol. 2010 ( 1 ) page： 1-6 2010.1

The (p, q)-total Labeling Problem for Trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMS AND COMPUTATION, PT 2 Vol. 6507 page： 49-+ 2010

Upper and Lower Bounds of Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol Reviewed

Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

PRINCIPLES OF DISTRIBUTED SYSTEMS Vol. 6490 page： 491-503 2010

Pattern Formation through Optimum Matching by Oblivious CORDA Robots Reviewed

Fujinaga Nao, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

PRINCIPLES OF DISTRIBUTED SYSTEMS Vol. 6490 page： 1-15 2010

木のL(2, 1)-ラベリングに対する線形時間アルゴリズム

蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之

研究報告アルゴリズム（AL） Vol. 2009 ( 7 ) page： 1-8 2009.11

Language：English Publishing type：Research paper (scientific journal)

グラフの k-L(2, 1) -ラベリングとは，頂点への 0 から k までの整数値の割り当てであり，隣接頂点間では少なくとも 2，距離 2 の頂点間では少なくとも 1 の差があるもののことを言う．L(2, 1) -ラベリング問題とは，グラフに対する k-L(2, 1) ラベリングの中で最小の k を求めるものである．この問題は，木幅が 2 のグラフに対してでも NP 困難であることが知られている．一方，多項式時間アルゴリズムは，路や閉路，木といった限られたクラスにしか知られておらず，木に対するアルゴリズムの計算量も 10 年以上 O(Δ4.5n) 時間であった（ただし，Δ はグラフの最大次数，n は木の頂点数）．この計算量は最近になって O(min{n1.75, Δ1.5n}) 時間へと改善されたが，線形時間で解けるかどうかは未解決であった．本論文では，これを解決する木の L(2, 1) -ラベリングに対する線形時間アルゴリズムを提案する．An L(2, 1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f (x)− f (y)| ≥ 2 if x and y are adjacent and |f (x)− f (y)| ≥ 1 if x and y are at distance 2, for all x and y in V(G). A k-L(2, 1)-labeling is an L(2, 1)-labeling f : V(G) → {0, . . . , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ4.5n) for more than a decade, and an O(min{n1.75, Δ1.5n})-time algorithm has appeared recently, where Δ is the maximum degree of T and n = |V(T)|, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem for L(2, 1)-labeling of trees by establishing a linear time algorithm.

1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))

伊藤健洋, 上原隆平, 小野廣隆, 玉木久夫, 宮本裕一郎

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2009 page： 78-79 2009.9

An O(n(1.75)) algorithm for L(2,1)-labeling of trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

THEORETICAL COMPUTER SCIENCE Vol. 410 ( 38-40 ) page： 3702-3710 2009.9

RA-007 Compressing method of Suffix Array whose decoding is fast Open Access

Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Vol. 8 ( 1 ) page： 43-50 2009.8

A Tight Upper Bound on the Hitting and the Cover times of Metropolis Walks

NONAKA Yoshiaki, ONO Hirotaka, SADAKANE Hiko, YAMASHITA Masafumi

IEICE technical report Vol. 109 ( 54 ) page： 9-12 2009.5

グラフの最小出次数最大化問題

朝廣雄一, Jesper Jansson, 宮野英次, 小野廣隆

研究報告アルゴリズム（AL） Vol. 2009 ( 7 ) page： 1-8 2009.5

Language：English Publishing type：Research paper (scientific journal)

MAXMINO という無向グラフの向き付け問題の一種について考える．無向枝重みつきグラフの向き付けを与えることにより，重み付き出次数を定義する（枝重みは正整数であるとする）．この問題は，グラフ中の最小重み付き出次数を最大化する問題である．本研究ではまず，MAXMINO は枝重みを {1 , 2} に限定し，かつ各頂点の（重みなし）次数が高々 3，さらにグラフが平面二部であるような場合でも強 NP 困難であり，P= NP でない限り，任意の定数 E ＞ 0 に対して多項式時間では 2 - E 近似不可能であることを示す．次にすべての枝重みが 1 である場合には，多項式時間で解くことができることを示す．これにより，枝重みが wmin よりも大きい枝数が O (log n)であるときにも，多項式時間で解くことができる．さらに，この手法により MAXMINO に対する単純な wmax / wmin 近似多項式時間アルゴリズムを得ることができる（wmax，wmin はそれぞれ枝重みの最大値，最小値)．最後に，入力グラフがカクタスである場合にも MAXMINO は多項式時間で解くことができることを示す．We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 - E for any constant E > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax / wmin -approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph.

連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用) Open Access

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1649 page： 252-259 2009.5

2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用) Open Access

穂坂祐輔, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1649 page： 203-209 2009.5

Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用) Open Access

野中良哲, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1649 page： 160-164 2009.5

DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

電子情報通信学会総合大会講演論文集 Vol. 2009 ( 1 ) page： "S-35"-"S-36" 2009.3

On Approximability of the Minimum Certificate Dispersal Problem

IZUMI Tomoko, IZUMI Taisuke, ONO Hirotaka, WADA Koich

IPSJ SIG Notes Vol. 2009 ( 18 ) page： 49-56 2009.2

Language：Japanese Publishing type：Research paper (scientific journal)

Assume that G is a graph and that R is a set of requests which is represented by a reachable ordered pair of nodes in G. The problem discussed in this paper requires us to assign edges to each node such that all requests in R are satisfied and the total number of edges all nodes have is minimized for a given G and R. To satisfy a request (u, v), a set of assigned edges to u and v must contain a path from u to v in G. This problem is called the Minimum Certificate Dispersal problem (MCD) and is NP-hard even if the input graph is restricted to a strongly connected one. In this paper, we consider approximability of MCD. We clarify an optimal approximability/inapproximability bound in terms of order: we prove the approximation ratio of MCD for strongly connected graphs is Ω(log n) and MCD has a polynomial time approximation algorithm whose factor is O(log n) (n is the number of nodes in G). In addition, we prove that when a given graph is restricted to an undirected graph, the MCD algorithm proposed in [11] guarantees 3/2 approximation ratio.

Drawing Borders Efficiently

Iwama Kazuo, Miyano Eiji, Ono Hirotaka, 岩間一雄, 宮野英次, 小野廣隆

Theory of Computing Systems Vol. 44 ( 2 ) page： 230-244 2009.2

Language：English Publishing type：Research paper (scientific journal)

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.

DOI： 10.1007/s00224-008-9117-y

Compressing method of Suffix Array whose decoding is fast

Drawing Borders Efficiently Reviewed

Iwama Kazuo, Miyano Eiji, Ono Hirotaka

THEORY OF COMPUTING SYSTEMS Vol. 44 ( 2 ) page： 230-244 2009.2

Hierarchical streaming algorithms for finding freaquent elements Open Access

Mizoguchi Ryu, Yamashita Masafumi, Ono Hirotaka

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 62-62 2009

Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 58-58 2009

A Succinct Representation of a Full Binary Tree.

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 59-59 2009

Convergence to Approximate Nash Equilibria in Incomplete Congestion Games Open Access

Yamada Yosuke, Ono Hirotaka, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 61-61 2009

A Linear Time Algorithm for L(2,1)-Labeling of Trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMS - ESA 2009, PROCEEDINGS Vol. 5757 page： 35-+ 2009

Graph Orientation to Maximize the Minimum Weighted Outdegree Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

2009 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-5 page： 1113-+ 2009

Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG Reviewed

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION Vol. 5532 page： 98-107 2009

Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem Reviewed

Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

COMPUTING AND COMBINATORICS, PROCEEDINGS Vol. 5609 page： 56-+ 2009

Route-Enabling Graph Orientation Problems Reviewed

Ito Takehiro, Miyamoto Yuichiro, Ono Hirotaka, Tamaki Hisao, Uehara Ryuhei

ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5878 page： 403-+ 2009

How to Design a Linear Cover Time Random Walk on a Finite Graph Reviewed

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS Vol. 5792 page： 104-+ 2009

A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems Reviewed

Ando Ei, Ono Hirotaka, Yamashita Masafumi

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS Vol. 5792 page： 89-103 2009

Speeding Up Local-Search Type Algorithms for Designing DNA Sequences under Thermodynamical Constraints Reviewed

Kawashimo Suguru, Ng Yen Kaow, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

DNA COMPUTING Vol. 5347 page： 168-178 2009

2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees

蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2008 page： 308-309 2008.9

RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文) Open Access

蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之

情報科学技術フォーラム講演論文集 Vol. 7 ( 1 ) page： 5-6 2008.8

近傍ハッシュ法によるエラー許容頻出パターン列挙

橋本英樹, 小野廣隆, 宇野毅明, 漆原秀子, 柳浦睦憲

情報処理学会研究報告バイオ情報学（BIO） Vol. 2008 ( 58 ) page： 63-66 2008.6

Language：English Publishing type：Research paper (scientific journal)

ゲノム配列から，ある機能発現に関わる遺伝子を発見したいという要望がある．このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で頻出する配列パターンの形をとることがしばしばある．本研究では，エラーを含む文字列集合から，ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する．エラーの影響から通常のパターン列挙と異なり，入力文字列には現れないパターンも列挙の対象となる．提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより，高速な全列挙を実現する．We propose a practically fast algorithm that enumerates all m-length substring patterns appearing in at least θ sequences among a given set of string sequences, where at most k errors are allowed for each appearance. The problem of enumerating such substring patterns is derived from the genome science, where frequent substring patterns allowing errors are candidates of a gene related to a certain function. From this context, some pattern should be enumerated even if it does not appear in any sequence, because it may match a sufficient number of sequences by allowing errors. In order to prevent overlooking such potential patterns, we propose a hash-based enumeration algorithm. The algorithm stores not only a substring pattern appearing in a sequence but also its neighboring patterns. By using several techniques/conditions to exclude non-frequent patterns, our algorithm achieves an efficient enumeration of frequent substring patterns allowing errors.

Minimum Weight Balanced Edge Cover Problem

HARADA Yuta, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

IPSJ SIG Notes Vol. 2008 ( 49 ) page： 33-40 2008.5

Language：Japanese Publishing type：Research paper (scientific journal)

For an undirected graph G=(V,E), an edge cover is defined as a set of edges that covers all vertices of V. It is known that a minimum edge cover can be found in polynomial time and forms a collection of star graphs. Previously, the authors of this paper consider the problem of finding a balanced edge cover where the degrees of star center vertices are balanced, and present an O(n^<1/2>m log Δ)-time polynomial time algorithm, where n, m and Δ are the number of vertices, the number of edges and the maximum degree of vertices, respectively. In this paper, for an edge-weighted graph, we consider the problem of finding a minimum weight balanced edge cover, that is, a balanced edge cover in which the total weights of edges is minimized. By characterizing the optimality as the existence of a certain path structure, we develop an O(n^3 m)-time algorithm.

On Necessary Conditions of Linear Cover Time Random Walks

NONAKA Yoshiaki, ONO Hirotaka, SADAKANE Hiko, YAMASHITA Masafumi

IEICE technical report Vol. 108 ( 29 ) page： 33-35 2008.5

Language：Japanese Publishing type：Research paper (scientific journal)

A random walk on a finite graph is a model that a token on a vertex repeatedly moves to an adjacent vertex randomly chosen according to some transition probability. The cover time of a random walk is a criterion of its speed, and roughly speaking, it is the expected number of steps in which the token visits all the vertices. Given a graph, we consider to design a fast random walk in terms of the cover time, by properly setting the transition probability. In this paper, we give necessary conditions for that the given graph has the cover time of O(n), where n is the number of vertices.

辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

深見浩和, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 182-188 2008.5

確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 170-175 2008.5

局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

川下優, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 27-34 2008.5

重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

原田雄太, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 57-64 2008.5

グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

野中良哲, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 73-78 2008.5

局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

来見田裕一, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 127-132 2008.5

3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

前村一哉, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 141-147 2008.5

Graph Classes and the Graph Orientation Problem to Minimize the Maximum Weighted Outdegree

ASAHIRO Yuichi, ONO Hirotaka, MIYANO Eiji

IPSJ SIG Notes Vol. 2008 ( 24 ) page： 43-50 2008.3

Language：Japanese Publishing type：Research paper (scientific journal)

Given an undirected graph with edge weights, we are asked to find an orientation, i.e., an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO. As previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tight thresholds of complexity: We show that MMO is (i) in P for cactuses, (ii) weakly NP-hard for multi outerplanar graphs and series-parallel graphs, and also (iii) strongly NP-hard for planar graphs and bipartite graphs.

DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

電子情報通信学会総合大会講演論文集 Vol. 2008 ( 1 ) page： "S-19"-"S-20" 2008.3

An O(n2) Hitting Time Random Walk Generated by Metropolis Hastings Algorithm

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2008 ( 0 ) page： 178-178 2008

The space complexity of the leader election in anonymous networks Reviewed

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

2008 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-8 page： 103-110 2008

Deductive Inference for the Interiors and Exteriors of Horn Theories Reviewed

Makino Kazuhisa, Ono Hirotaka

ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5369 page： 390-+ 2008

The Balanced Edge Cover Problem Reviewed

Harada Yuta, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5369 page： 246-257 2008

Dynamic neighborhood searches for thermodynamically designing DNA sequence Reviewed

Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

DNA COMPUTING Vol. 4848 page： 130-+ 2008

A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs Open Access

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

情報科学技術フォーラム講演論文集 page： 7-8 2008

An O(n<(1.75)) algorithm for L(2,1)-labeling of trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHM THEORY - SWAT 2008 Vol. 5124 page： 185-+ 2008

混合ドミノタイリングの連結性

小野廣隆, 貞廣泰造

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 107 ( 258 ) page： 19-24 2007.10

Language：English Publishing type：Research paper (scientific journal)

正方-八方格子の双対グラフ上の単連結部分グラフにおける完全マッチングについて,局所変形連結性の観点から研究する.これらのグラフは二部性を持たずある意味で不純物を含んでいるため,従来の研究で使われてきた高さ関数を用いた手法を利用することは出来ない.本研究では組合せ的手法を用いて,連結性を保証する最小の局所変形集合を与える:すなわち,これらのグラフ上の任意の完全マッチング同士が,二辺だけを動かす局所変形を繰り返すことにより移りあうことを示す.この結果から完全マッチング全体を状態集合とする簡易なマルコフ連鎖を構成でき,またその定常状態を一様とすることができる.計算シミュレーションでは顕著な統計的性質が観測された.

ホーン理論の内包・外包に対する演繹推論

牧野和久, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 107 ( 127 ) page： 33-39 2007.6

Language：English Publishing type：Research paper (scientific journal)

本論文ではホーン知識ベースの内包・外包に対する演繹推論について考える.知識ベースの内包・外包はその安定性を測るものとして,Makino, Ibaraki [11]により提案された.本論文ではホーン関数(式表現)の内包に対する演繹推論を行う線形時間アルゴリズムを与え,外包に対する演繹推論がco-NP完全であることを示す.またホーン知識がモデル表現で与えられた場合,演繹推論は内包・外包共に計算困難であることを示す.外包のホーン包絡に関しては,モデル表現においては線形時間で解くことができる一方,式表現においてはco-NP完全となることを示す.また各計算困難なクラスにおいて,多項式時間で解ける部分クラスについても議論する.

負荷分散枝被覆問題に対する最適性とアルゴリズム

原田雄太, 小野廣隆, 定兼邦彦, 山下雅史

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 107 ( 73 ) page： 43-50 2007.5

Language：English Publishing type：Research paper (scientific journal)

無向グラフG=(V,E)において,全ての頂点が少なくとも1つの枝に接しているような枝の集合を枝被覆と呼ぶ.特に最小枝被覆は多項式時間で得られ,またスターグラフの集合により構成されることが知られている.本研究では,各スターの枝数が均等になるような枝被覆を求める負荷分散枝被覆問題を扱う.この問題の応用例として,センサーネットワークの構造最適化などが挙げられる.この目的達成のために,被覆枝における次数に関する狭義単調増加凸関数の和の最小化問題として問題を定式化し,その最適性がある種の交互パスの非存在として特徴付けられることを示す.またこの特徴付けを利用し,最適な枝被覆が最小枝被覆であること,被覆枝における次数列の辞書順が最小となること,最大次数が最小化されることを示す.さらに,この特徴を基にしたO(|V||E|)時間のアルゴリズムを提案する.

On Approximation of Bookmark Assignments

ASAHIRO Yuichi, MIYANO Eiji, ONO Hirotaka, MURATA Toshihide

IEICE technical report Vol. 107 ( 73 ) page： 1-6 2007.5

Language：Japanese Publishing type：Research paper (scientific journal)

Consider a rooted directed acyclic graph G=(V,E)with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor(1-1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than(1-1/e)unless NP&subE;DTIME(N^<o(loglogN)>), where is the size of the inputs.

負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用) Open Access

$k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用) Open Access

坂田敦, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 269-275 2007.5

原田雄太, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 101-108 2007.5

境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用) Open Access

深見浩和, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 139-144 2007.5

確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用) Open Access

安藤映, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 202-209 2007.5

ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用) Open Access

前村一哉, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 238-242 2007.5

部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用) Open Access

後藤隆元, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 243-249 2007.5

局所探索法に基づくDNA 配列設計手法(計算機科学の理論とその応用) Open Access

川下優, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 250-257 2007.5

センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用) Open Access

佐薙光樹, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 264-268 2007.5

Graph orientation algorithms to minimize the maximum outdegree Reviewed Open Access

Asahiro Yuichi, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE Vol. 18 ( 2 ) page： 197-215 2007.4

Failure Detectors for Solving k-Set Agreement

SAKATA Atsushi, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

IEICE technical report Vol. 106 ( 566 ) page： 1-6 2007.3

Language：Japanese Publishing type：Research paper (scientific journal)

Failure detectors are distributed oracles that provide each process with information about failures of other processes in distributed systems. It is known that many problems are unsolvable in asynchronous distributed systems if crash failures occur. For such unsolvable problems, failure detectors can be used to make them solvable. How strong information failure detectors should provide, that is, the weakest failure detectors for a certain problem are intensively studied from both theoretical and practical viewpoints. In this paper, we propose two new failure detectors classes, (k-Ω,Σ) and (Ω,Σ_k>), for solving k-Set Agreement problem, where both are generalizations of (Ω,Σ) that is a class of the weakest failure detectors for consensus problem. Furthermore, we consider the reducibility between these failure detector classes and another failure detector class, (Ω^k,Σ), which is also proposed for k-Set Agreement in a related study.

Collecting Moving Objects

ASAHIRO Yuichi, ONO Hirotaka, MIYANO Eiji, YAMASHITA Masafumi

The Journal of the Institute of Electronics, Information and Communication Engineers Vol. 90 ( 3 ) page： 245-247 2007.2

Exploration of Scale-Free Graphs with Degree Information Open Access

Kurumida Yuichi, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2007 ( 0 ) page： 95-95 2007

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS Vol. 4508 page： 167-+ 2007

Approximation Ratio of Algorithms for Constructing Evolutionary Trees from Rooted Triplets Open Access

Maemura Kazuya, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2007 ( 0 ) page： 85-85 2007

Thermodynamically DNA Sequences Design based on Local Search Open Access

Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2007 ( 0 ) page： 93-93 2007

On approximation of bookmark assignments Reviewed

Asahiro Yuichi, Miyano Eiji, Murata Toshihide, Ono Hirotaka

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS Vol. 4708 page： 115-+ 2007

Drawing borders efficiently Reviewed

Iwama Kazuo, Miyano Eiji, Ono Hirotaka

FUN WITH ALGORITHMS, PROCEEDINGS Vol. 4475 page： 213-+ 2007

How to collect balls moving in the Euclidean plane Reviewed

Asahiro Yuichi, Horiyama Takashi, Makino Kazuhisa, Ono Hirotaka, Sakuma Toshinori, Yamashita Masafumi

DISCRETE APPLIED MATHEMATICS Vol. 154 ( 16 ) page： 2247-2262 2006.11

DNA Sequence Design by Dynamic Neighborhood Searches

KAWASHIMO Suguru, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

IEICE technical report Vol. 106 ( 63 ) page： 47-54 2006.5

Language：Japanese Publishing type：Research paper (scientific journal)

In recent years, DNA sequence sets are used in various fields such as nanotechnology and nanocomputing. Since there are several applications using the sequence sets, the sequence sets need to satisfy several constraints depending on the applications. Since several constraints are combinatorial, we consider the sequence sets design problem where the sequence sets are used to solve combinatorial problems. For the purpose, we focus on the overlapping measure which is more combinatorial than other constraints. Then, we propose a local-search based approximation algorithm. To deal with this, we adopt a dynamic neighorhood search frame work, called Variable Neighborhood Search and Variable Depth Search. The computational experiments show that generated sequence sets are as good as the ones generated by exiting methods, or better.

DNA Sequence Desgin Using Hidden Markov Models

MAEMURA Kazuya, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

IEICE technical report Vol. 106 ( 63 ) page： 39-46 2006.5

Language：Japanese Publishing type：Research paper (scientific journal)

DNA computing is a new computation paradigm to take reaction process of DNA as computation. The design of DNA sequence is a one of crucial research topics in DNA computing. We have to prepare DNA sequences that satisfy many constraints to react DNA as we expected. In our research, we propose sequence design using Hidden Markov Models. Hidden Markov Model is a stochastic model utilizing Markov process. In this paper, as a test of this method, we show experiments and their results of sequence design of DNA whose minimum free energy is small.