Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 121 - 140 of about 260 ／ All the affair displays >>

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.

CiNii Research

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

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へ遷移させる最短の系列を多項式時間で見つけることができる.

CiNii Research

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