Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 81 - 100 of about 260 ／ All the affair displays >>

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

Web of Science

Scopus

CiNii Research

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

Open Access

Web of Science

Scopus

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

Reallocation Problems with Minimum Completion Time.

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

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka