Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 61 - 80 of about 260 ／ All the affair displays >>

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

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

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka