Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 181 - 200 of about 236 ／ All the affair displays >>

A Linear Time Algorithm for L(2,1)-Labeling of Trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMS - ESA 2009, PROCEEDINGS Vol. 5757 page： 35-+ 2009

How to Design a Linear Cover Time Random Walk on a Finite Graph Reviewed

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS Vol. 5792 page： 104-+ 2009

A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems Reviewed

Ando Ei, Ono Hirotaka, Yamashita Masafumi

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS Vol. 5792 page： 89-103 2009

Speeding Up Local-Search Type Algorithms for Designing DNA Sequences under Thermodynamical Constraints Reviewed

Kawashimo Suguru, Ng Yen Kaow, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

DNA COMPUTING Vol. 5347 page： 168-178 2009

Route-Enabling Graph Orientation Problems Reviewed

Ito Takehiro, Miyamoto Yuichiro, Ono Hirotaka, Tamaki Hisao, Uehara Ryuhei

ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5878 page： 403-+ 2009

Graph Orientation to Maximize the Minimum Weighted Outdegree Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

2009 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-5 page： 1113-+ 2009

Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG Reviewed

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION Vol. 5532 page： 98-107 2009

Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem Reviewed

Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

COMPUTING AND COMBINATORICS, PROCEEDINGS Vol. 5609 page： 56-+ 2009

2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees

蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2008 page： 308-309 2008.9

RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)

蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之

情報科学技術フォーラム講演論文集 Vol. 7 ( 1 ) page： 5-6 2008.8

近傍ハッシュ法によるエラー許容頻出パターン列挙

橋本英樹, 小野廣隆, 宇野毅明, 漆原秀子, 柳浦睦憲

情報処理学会研究報告バイオ情報学（BIO） Vol. 2008 ( 58 ) page： 63-66 2008.6

Language：English Publishing type：Research paper (scientific journal)

ゲノム配列から，ある機能発現に関わる遺伝子を発見したいという要望がある．このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で頻出する配列パターンの形をとることがしばしばある．本研究では，エラーを含む文字列集合から，ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する．エラーの影響から通常のパターン列挙と異なり，入力文字列には現れないパターンも列挙の対象となる．提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより，高速な全列挙を実現する．We propose a practically fast algorithm that enumerates all m-length substring patterns appearing in at least θ sequences among a given set of string sequences, where at most k errors are allowed for each appearance. The problem of enumerating such substring patterns is derived from the genome science, where frequent substring patterns allowing errors are candidates of a gene related to a certain function. From this context, some pattern should be enumerated even if it does not appear in any sequence, because it may match a sufficient number of sequences by allowing errors. In order to prevent overlooking such potential patterns, we propose a hash-based enumeration algorithm. The algorithm stores not only a substring pattern appearing in a sequence but also its neighboring patterns. By using several techniques/conditions to exclude non-frequent patterns, our algorithm achieves an efficient enumeration of frequent substring patterns allowing errors.

Minimum Weight Balanced Edge Cover Problem

HARADA Yuta, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

IPSJ SIG Notes Vol. 2008 ( 49 ) page： 33-40 2008.5

Language：Japanese Publishing type：Research paper (scientific journal)

For an undirected graph G=(V,E), an edge cover is defined as a set of edges that covers all vertices of V. It is known that a minimum edge cover can be found in polynomial time and forms a collection of star graphs. Previously, the authors of this paper consider the problem of finding a balanced edge cover where the degrees of star center vertices are balanced, and present an O(n^<1/2>m log Δ)-time polynomial time algorithm, where n, m and Δ are the number of vertices, the number of edges and the maximum degree of vertices, respectively. In this paper, for an edge-weighted graph, we consider the problem of finding a minimum weight balanced edge cover, that is, a balanced edge cover in which the total weights of edges is minimized. By characterizing the optimality as the existence of a certain path structure, we develop an O(n^3 m)-time algorithm.

On Necessary Conditions of Linear Cover Time Random Walks

NONAKA Yoshiaki, ONO Hirotaka, SADAKANE Hiko, YAMASHITA Masafumi

IEICE technical report Vol. 108 ( 29 ) page： 33-35 2008.5

Language：Japanese Publishing type：Research paper (scientific journal)

A random walk on a finite graph is a model that a token on a vertex repeatedly moves to an adjacent vertex randomly chosen according to some transition probability. The cover time of a random walk is a criterion of its speed, and roughly speaking, it is the expected number of steps in which the token visits all the vertices. Given a graph, we consider to design a fast random walk in terms of the cover time, by properly setting the transition probability. In this paper, we give necessary conditions for that the given graph has the cover time of O(n), where n is the number of vertices.

辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)

深見浩和, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 182-188 2008.5

局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)

川下優, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 27-34 2008.5

重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)

原田雄太, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 57-64 2008.5

グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)

野中良哲, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 Vol. 1599 page： 73-78 2008.5