研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 201 - 220 件目／全件表示 >>

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

情報処理学会研究報告アルゴリズム（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.

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はグラフの頂点数でる.また,到達時間とはある頂点を出発し,別のある頂点へ達するまでに要する遷移数の期待値である.

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

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

情報科学技術フォーラム講演論文集頁： 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月

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

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

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

牧野和久, 小野廣隆

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

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

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

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

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

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

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

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

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

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

電子情報通信学会技術研究報告. 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は入力サイズを表している.

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

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

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

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

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

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

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

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

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

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

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

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