研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 260 件中 221 - 240 件目／全件表示 >>

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

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

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

局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

来見田裕一, 小野廣隆, 定兼邦彦, 山下雅史

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

3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

前村一哉, 小野廣隆, 定兼邦彦, 山下雅史

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

確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて) Open Access

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

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

最大出次数最小化問題の各種グラフクラスに対する計算複雑さ

朝廣雄一, 小野廣隆, 宮野英次

情報処理学会研究報告アルゴリズム（AL） 2008 巻 ( 24 ) 頁： 43-50 2008年3月

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

辺重みつき無向グラフが与えられ，辺の向き付けを求める問題 MMO を考える．MMO の目的は重みつき出次数の最大値を最小化することである．MMO は木に対してはΡ，平面二部グラフに対しては強 ΝΡ- 困難，一般のグラフに対してはNP- 困難であることが，過去の研究により知られている．しかし，これらのグラフクラス間には隔たりがあり，困難さの境界が厳密でない本稿の目的は，MMO の困難さの境界を明らかにすることであり，カクタス(木はカクタスの部分クラス）に対しては Ρ，多重辺を持つ外平面グラフや直並列グラフに対しては弱ΝΡ- 困難，平面グラフと二部グラフに対しては強ΝΡ- 困難であることを示す．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 Ρfor trees, weak .ΝΡ- hard for planar bipartite graphs, and strong ΝΡ- 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 Ρ for cactuses, (ii) weakly ΝΡ- hard for multi outerplanar graphs and series-parallel graphs, and also (iii) strongly ΝΡ-hard for planar graphs and bipartite graphs.

CiNii Research

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

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

電子情報通信学会総合大会講演論文集 2008 巻 ( 1 ) 頁： "S-19"-"S-20" 2008年3月

メトロポリス・ヘイスティングアルゴリズムに基づくO(n2)到達時間ランダムウォーク

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

電気関係学会九州支部連合大会講演論文集 2008 巻 ( 0 ) 頁： 178-178 2008年

掲載種別：研究論文（学術雑誌）

グラフ上のランダムウォークにおいて,隣接頂点への遷移確率をメトロポリス・ヘイスティングアルゴリズムに基づいて定義することで,到達時間がO(n^2)となるランダムウォークを実現することが出来る.ここで,nはグラフの頂点数でる.また,到達時間とはある頂点を出発し,別のある頂点へ達するまでに要する遷移数の期待値である.

CiNii Research

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

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

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

Dynamic neighborhood searches for thermodynamically designing DNA sequence 査読有り

Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

DNA COMPUTING 4848 巻頁： 130-+ 2008年

An O(n<(1.75)) algorithm for L(2,1)-labeling of trees 査読有り

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHM THEORY - SWAT 2008 5124 巻頁： 185-+ 2008年

The space complexity of the leader election in anonymous networks 査読有り

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

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

Deductive Inference for the Interiors and Exteriors of Horn Theories 査読有り

Makino Kazuhisa, Ono Hirotaka

ALGORITHMS AND COMPUTATION, PROCEEDINGS 5369 巻頁： 390-+ 2008年

The Balanced Edge Cover Problem 査読有り

Harada Yuta, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

ALGORITHMS AND COMPUTATION, PROCEEDINGS 5369 巻頁： 246-257 2008年

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

小野廣隆, 貞廣泰造

電子情報通信学会技術研究報告. COMP, コンピュテーション 107 巻 ( 258 ) 頁： 19-24 2007年10月

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

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

CiNii Research

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

牧野和久, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション 107 巻 ( 127 ) 頁： 33-39 2007年6月

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

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

CiNii Research

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

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

電子情報通信学会技術研究報告. COMP, コンピュテーション 107 巻 ( 73 ) 頁： 43-50 2007年5月

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

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

CiNii Research

ブックマーク問題の近似について

朝廣雄一, 宮野英次, 小野廣隆, 村田俊英

電子情報通信学会技術研究報告. COMP, コンピュテーション 107 巻 ( 73 ) 頁： 1-6 2007年5月

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

ハイパーリンクの集合Eで連結されたウェブページの集合Vを表した根付き有向非巡回グラフG=(V,E)を考える.それぞれのノードvは,ユーザがノードvを閲覧するアクセス頻度を持っている.アクセスコストは,根ノードrからあるノードvに到達するためのステップ数の期待値で定義される.ブックマークは,グラフGの根ノードrに付加するショートカットリンクであり,アクセスコストを小さくする効果がある.ブックマーク問題は,アクセスコストを最も改善するようなブックマーク集合を求める問題である.本稿では,ブックマーク問題に対する(1-1/e)近似アルゴリズムを示す.またNP&subE;DTIME(N^<o(loglogN)>)を満たさない場合には,(1-1/e)よりも良い近似比を持つ多項式時間のアルゴリズムは存在しないことを示す.ここで,Nは入力サイズを表している.

CiNii Research

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

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

数理解析研究所講究録 1554 巻頁： 269-275 2007年5月

ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用) Open Access

前村一哉, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 1554 巻頁： 238-242 2007年5月

部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用) Open Access

後藤隆元, 小野廣隆, 定兼邦彦[他]

数理解析研究所講究録 1554 巻頁： 243-249 2007年5月

　前のページ - 次のページ　

<小野 廣隆>

論文 - 小野 廣隆

<小野　廣隆>

論文 - 小野　廣隆