Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 21 - 40 of about 260 ／ All the affair displays >>

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

Web of Science

Scopus

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

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

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

Open Access

Web of Science

Scopus

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

Open Access

Scopus

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.

Scopus

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

Scopus

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

Scopus

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

Open Access

Scopus

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

Scopus

Hedonic Seat Arrangement Problems Reviewed International coauthorship

小野廣隆

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

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka