Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 201 - 220 of about 236 ／ All the affair displays >>

Graph Classes and the Graph Orientation Problem to Minimize the Maximum Weighted Outdegree

ASAHIRO Yuichi, ONO Hirotaka, MIYANO Eiji

IPSJ SIG Notes Vol. 2008 ( 24 ) page： 43-50 2008.3

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

Given an undirected graph with edge weights, we are asked to find an orientation, i.e., an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO. As previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tight thresholds of complexity: We show that MMO is (i) in P for cactuses, (ii) weakly NP-hard for multi outerplanar graphs and series-parallel graphs, and also (iii) strongly NP-hard for planar graphs and bipartite graphs.

DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

電子情報通信学会総合大会講演論文集 Vol. 2008 ( 1 ) page： "S-19"-"S-20" 2008.3

An O(n2) Hitting Time Random Walk Generated by Metropolis Hastings Algorithm

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2008 ( 0 ) page： 178-178 2008

A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs

安藤映, 小野廣隆, 定兼邦彦, 山下雅史

情報科学技術フォーラム講演論文集 page： 7-8 2008

Dynamic neighborhood searches for thermodynamically designing DNA sequence Reviewed

Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

DNA COMPUTING Vol. 4848 page： 130-+ 2008

An O(n<(1.75)) algorithm for L(2,1)-labeling of trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHM THEORY - SWAT 2008 Vol. 5124 page： 185-+ 2008

The space complexity of the leader election in anonymous networks Reviewed

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

2008 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-8 page： 103-110 2008

Deductive Inference for the Interiors and Exteriors of Horn Theories Reviewed

Makino Kazuhisa, Ono Hirotaka

ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5369 page： 390-+ 2008

The Balanced Edge Cover Problem Reviewed

Harada Yuta, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5369 page： 246-257 2008

混合ドミノタイリングの連結性

小野廣隆, 貞廣泰造

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 107 ( 258 ) page： 19-24 2007.10

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

正方-八方格子の双対グラフ上の単連結部分グラフにおける完全マッチングについて,局所変形連結性の観点から研究する.これらのグラフは二部性を持たずある意味で不純物を含んでいるため,従来の研究で使われてきた高さ関数を用いた手法を利用することは出来ない.本研究では組合せ的手法を用いて,連結性を保証する最小の局所変形集合を与える:すなわち,これらのグラフ上の任意の完全マッチング同士が,二辺だけを動かす局所変形を繰り返すことにより移りあうことを示す.この結果から完全マッチング全体を状態集合とする簡易なマルコフ連鎖を構成でき,またその定常状態を一様とすることができる.計算シミュレーションでは顕著な統計的性質が観測された.

ホーン理論の内包・外包に対する演繹推論

牧野和久, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 107 ( 127 ) page： 33-39 2007.6

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

本論文ではホーン知識ベースの内包・外包に対する演繹推論について考える.知識ベースの内包・外包はその安定性を測るものとして,Makino, Ibaraki [11]により提案された.本論文ではホーン関数(式表現)の内包に対する演繹推論を行う線形時間アルゴリズムを与え,外包に対する演繹推論がco-NP完全であることを示す.またホーン知識がモデル表現で与えられた場合,演繹推論は内包・外包共に計算困難であることを示す.外包のホーン包絡に関しては,モデル表現においては線形時間で解くことができる一方,式表現においてはco-NP完全となることを示す.また各計算困難なクラスにおいて,多項式時間で解ける部分クラスについても議論する.

負荷分散枝被覆問題に対する最適性とアルゴリズム

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

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 107 ( 73 ) page： 43-50 2007.5

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

無向グラフG=(V,E)において,全ての頂点が少なくとも1つの枝に接しているような枝の集合を枝被覆と呼ぶ.特に最小枝被覆は多項式時間で得られ,またスターグラフの集合により構成されることが知られている.本研究では,各スターの枝数が均等になるような枝被覆を求める負荷分散枝被覆問題を扱う.この問題の応用例として,センサーネットワークの構造最適化などが挙げられる.この目的達成のために,被覆枝における次数に関する狭義単調増加凸関数の和の最小化問題として問題を定式化し,その最適性がある種の交互パスの非存在として特徴付けられることを示す.またこの特徴付けを利用し,最適な枝被覆が最小枝被覆であること,被覆枝における次数列の辞書順が最小となること,最大次数が最小化されることを示す.さらに,この特徴を基にしたO(|V||E|)時間のアルゴリズムを提案する.

On Approximation of Bookmark Assignments

ASAHIRO Yuichi, MIYANO Eiji, ONO Hirotaka, MURATA Toshihide

IEICE technical report Vol. 107 ( 73 ) page： 1-6 2007.5

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

Consider a rooted directed acyclic graph G=(V,E)with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor(1-1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than(1-1/e)unless NP&subE;DTIME(N^<o(loglogN)>), where is the size of the inputs.

$k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用)

坂田敦, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 269-275 2007.5

負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用)

原田雄太, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 101-108 2007.5

境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用)

深見浩和, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 139-144 2007.5

確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)

安藤映, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 Vol. 1554 page： 202-209 2007.5