研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 181 - 200 件目／全件表示 >>

A Linear Time Algorithm for L(2,1)-Labeling of Trees 査読有り

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMS - ESA 2009, PROCEEDINGS 5757 巻頁： 35-+ 2009年

How to Design a Linear Cover Time Random Walk on a Finite Graph 査読有り

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS 5792 巻頁： 104-+ 2009年

A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems 査読有り

Ando Ei, Ono Hirotaka, Yamashita Masafumi

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS 5792 巻頁： 89-103 2009年

Speeding Up Local-Search Type Algorithms for Designing DNA Sequences under Thermodynamical Constraints 査読有り

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

DNA COMPUTING 5347 巻頁： 168-178 2009年

Route-Enabling Graph Orientation Problems 査読有り

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

ALGORITHMS AND COMPUTATION, PROCEEDINGS 5878 巻頁： 403-+ 2009年

Graph Orientation to Maximize the Minimum Weighted Outdegree 査読有り

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

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

Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG 査読有り

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION 5532 巻頁： 98-107 2009年

Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem 査読有り

Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

COMPUTING AND COMBINATORICS, PROCEEDINGS 5609 巻頁： 56-+ 2009年

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

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

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2008 巻頁： 308-309 2008年9月

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

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

情報科学技術フォーラム講演論文集 7 巻 ( 1 ) 頁： 5-6 2008年8月

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

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

情報処理学会研究報告バイオ情報学（BIO） 2008 巻 ( 58 ) 頁： 63-66 2008年6月

記述言語：英語掲載種別：研究論文（学術雑誌）

ゲノム配列から，ある機能発現に関わる遺伝子を発見したいという要望がある．このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で頻出する配列パターンの形をとることがしばしばある．本研究では，エラーを含む文字列集合から，ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する．エラーの影響から通常のパターン列挙と異なり，入力文字列には現れないパターンも列挙の対象となる．提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより，高速な全列挙を実現する．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.

最小重み負荷分散枝被覆について

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

情報処理学会研究報告アルゴリズム（AL） 2008 巻 ( 49 ) 頁： 33-40 2008年5月

記述言語：日本語掲載種別：研究論文（学術雑誌）

無向グラフ G＝(V E)に対し，V の全ての点を被覆するような枝集合のことを枝被覆と呼ぶ．最小の枝被覆はスターグラフの集合の形をとり，また多項式時間で得られることが知られている．以前著者らは，負荷分散枝被覆問題，すなわち枝被覆が与えるスターグラフの中心頂点の次数が均等化されたような枝被覆を求める問題を考え，これを求める O(n1/2m log△)時間アルゴリズムを提案している．本論文では，枝に重みが付加されたグラフに対し最小重みの負荷分散枝被覆を求める問題について考える．最適解に対する特徴づけとしてある性質を持ったパス構造の存在性の形で与え，それに基づいた O(n3m）時間アルゴリズムを与える．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(n1/2m log△)-time polynomial time algorithm, where n, m and A 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(n3m)-time algorithm.

グラフ上の線形 Cover Time ランダムウォーク実現の必要条件

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

電子情報通信学会技術研究報告. COMP, コンピュテーション 108 巻 ( 29 ) 頁： 33-35 2008年5月

記述言語：日本語掲載種別：研究論文（学術雑誌）

有限グラフ上のランダムウォークとは,グラフ上に置かれた粒子が,その隣接点へとある確率にしたがってランダムに遷移するモデルである.ランダムウォークの速さの指標として,cover timeがある.これはある頂点を出発した粒子が,全ての頂点を訪問するために要する遷移数の期待値である.本研究の目的は,グラフが与えられたときよりcover timeの小さなランダムウォークを設計することである.本発表では,n頂点からなるグラフに対してcover timeがO(n)であるランダムウォークを設計可能であるための必要条件を示す.

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

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

数理解析研究所講究録 1599 巻頁： 182-188 2008年5月

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

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

数理解析研究所講究録 1599 巻頁： 27-34 2008年5月

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

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

数理解析研究所講究録 1599 巻頁： 57-64 2008年5月

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

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

数理解析研究所講究録 1599 巻頁： 73-78 2008年5月