Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

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

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

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

Web of Science

Scopus

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

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

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

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

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

Reallocation Problems with Minimum Completion Time.

Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

COCOON Vol. 13595 page： 292 - 304 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

Scopus

Hedonic seat arrangement problems

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.

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

Fair Ride Allocation on a Line

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

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 Open Access

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

<p>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.</p>

DOI： 10.1587/transinf.2023fcl0003

On a Spectral Lower Bound of Treewidth Open Access

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

<p>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)].</p>

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

Scopus

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

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka