研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 260 件中 161 - 180 件目／全件表示 >>

DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)

溝口隆, 小野廣隆, 来嶋秀治, 山下雅史

電子情報通信学会総合大会講演論文集 2011 巻 ( 1 ) 頁： "S-11"-"S-12" 2011年2月

Broadcastings and digit tilings on three-dimensional torus networks 査読有り Open Access

Okazaki Ryotaro, Ono Hirotaka, Sadahiro Taizo, Yamashita Masafumi

THEORETICAL COMPUTER SCIENCE 412 巻 ( 4-5 ) 頁： 307-319 2011年2月

グラフトポロジーを利用した高速ランダムウォークの設計

小野廣隆

旭硝子財団助成研究成果報告頁： 1-5 2011年

The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Delta+2 査読有り

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

COMBINATORIAL ALGORITHMS 6460 巻頁： 103-+ 2011年

Approximability of the Path-Distance-Width for AT-free Graphs 査読有り

Otachi Yota, Saitoh Toshiki, Yamanaka Katsuhisa, Kijima Shuji, Okamoto Yoshio, Ono Hirotaka, Uno Yushi, Yamazaki Koichi

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE 6986 巻頁： 271-+ 2011年

On the Approximability of Minimum Topic Connected Overlay and Its Special Instances 査読有り

Hosoda Jun, Hromkovic Juraj, Izumi Taisuke, Ono Hirotaka, Steinova Monika, Wada Koichi

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011 6907 巻頁： 376-387 2011年

最大支配問題

宮野英次, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション 110 巻 ( 325 ) 頁： 53-60 2010年11月

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

グラフにおける頂点/辺支配集合問題の新しい亜種について考える.ある頂点はその頂点自身と隣接点を支配すると言い,同様にある辺はその辺自身と隣接する辺を支配すると言う.グラフG=(V,E)と正整数kが与えられたとき,k-頂点(k-辺)支配問題(それぞれ以下k-MaxVD, k-MaxEDと呼ぶ)は高々サイズkの頂点の部分集合D_V&subE;V(D_E&subE;E)の中で,支配する頂点集合(また辺集合)のサイズを最大化するものを求める問題である.本論文では,まずこの問題に対して単純な貪欲アルゴリズムがk-MaxVD, k-MaxEDいずれに対しても近似比(1-1/e)を達成することを示す.次にP≠NPの条件下で,k-MaxVEに対してこの近似比が多項式時間アルゴリズムの最善であることを示す.さらにP≠NPの条件下で,k-MaxEDに対して1303/1304よりも良い近似比の多項式時間アルゴリズムが存在しないことを示す.一方,kがグラフの最小最大マッチングのサイズを超えないという条件下では,k-MaxEDに対して近似比3/4の多項式時間アルゴリズムが存在することを示す.

CiNii Research

自己安定リーダー選挙MPPにおける領域複雑度の上下界について

溝口隆, 小野廣隆, 来嶋秀治, 山下雅史

研究報告アルゴリズム（AL） 2010 巻 ( 4 ) 頁： 1-5 2010年11月

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

本論文は，自己安定リーダー選挙メディエイテッドポピュレーションプロトコル (SS-LE MPP) の領域複雑度に関する研究結果である．Cai，Izumi and Wada (2009) は n エージェントに対する自己安定リーダー選挙ポピュレーションプロトコル (SS-LE PP) は少なくとも n 個のエージェント状態を必要とすることを示した．さらに n エージェントに対する SS-LE MPP のうちエージェント状態数が n であるプロトコルを与えた．MPP は Chatzigiannakis，Michail and Spirakis (2009) によって紹介された．MPP は分散ネットワークモデルの 1 つで，各エージェント間に局所的なメモリを追加した PP の拡張モデルである．一般的に MPP は PP よりも計算能力が高いことが知られている．一方で SS-LE のエージェント状態に対する空間複雑度の減少可能性については知られていない．本稿では，n エージェントの SS-LE MPP のうちエージェント状態数が n-1 であり，各エージェント間に 1 ビットのメモリが与えられたプロトコルを与える．This paper investigates the space complexity of a self stabilizing leader election in a mediated population protocol (SS-LE MPP). Cai, Izumi and Wada (2009) showed that SS-LE in a population protocol (SS-LE PP) for n agents requires at least n agent-states, and gave a SS-LE PP with n agent-states for n agents. MPP is a model of distributed computation, introduced by Chatzigiannakis, Michail and Spirakis (2009) as an extension of PP allowing an extra memory on every agents pair. While they showed that MPP is stronger than PP in general, it was not known if a MPP can really reduce the space complexity of SS-LE with respect to agent-states. We in this paper give a SS-LE MPP with n - 1 agent-states and a single bit memory on every agents pair for n agents.

CiNii Research

木の(<i>p</i>, <i>q</i>)-全ラベリング問題

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

研究報告アルゴリズム（AL） 2010 巻 ( 2 ) 頁： 1-8 2010年11月

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

グラフ G の k-(p,q)-全ラベリングとは，G の節点と辺への 0 から k までの整数値の割当てであり，節点とそれに接続する辺の間では少なくとも p，隣接する 2 節点間または 2 辺間では少なくとも q の差があるもののことをいう．G の (p, q)-全ラベリング数 λTp;q(G) は，k がとりうる値の最小値として定義される．G の (p, q)-全ラベリング問題とは，ラベリング数 λTp;q(G) を求める問題である．本研究では，いくつかのグラフクラスのグラフの (p, q)-全ラベリング数に対して新しい上界と下界を与える．とくに，グラフが木の場合にはタイトな上界と下界を与える．また，グラフが木で p≦3q/2 の場合に (p, q)-全ラベリング問題を解く線形時間アルゴリズムを与え，さらに最大次数が 4 以上という仮定が加わった場合，λTp;q(T) を実現する木Tを完全に特徴づけられることも示す．この結果は，(p; q)-全ラベリング問題の一般化である L (p; q)-ラベリング問題が q が p の約数でないすべての (p; q) の組に対し NP 困難であることと対照的である．A (p,q)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set of nonnegative integers such that |f(x)-f(y)| ≧ p if x is a vertex and y is an edge incident to x, and |f(x)-f(y)| ≧ q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) ∪ E(G). A k-(p,q)-total labeling is a (p,q)-total labeling f:V(G) ∪ E(G) → {0,...,k}, and the (p,q)-total labeling problem asks the minimum k, which we denote by λTp,q(G), among all possible assignments. In this paper, we first give new upper and lower bounds on λTp,q(G) for some classes of graphs G, in particular, tight bounds on λTp,q(T) for trees T. We then show that if p ≦ 3q/2, the problem for trees T is linearly solvable, and give a complete characterization of trees achieving λTp,q(T) if in addition Δ ≧ 4 holds, where Δ is the maximum degree of T. It is contrasting to the fact that the L(p,q)-labeling problem, which is a generalization of the (p,q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p.

CiNii Research

A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文) Open Access

山田陽介, 小野廣隆, 来嶋秀治, 山下雅史

情報科学技術フォーラム講演論文集 9 巻 ( 1 ) 頁： 231-232 2010年8月

A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文) Open Access

田中洋輔, 小野廣隆, 定兼邦彦, 山下雅史

情報科学技術フォーラム講演論文集 9 巻 ( 1 ) 頁： 205-206 2010年8月

A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文) Open Access

馬場雅大, 小野廣隆, 定兼邦彦, 山下雅史

情報科学技術フォーラム講演論文集 9 巻 ( 1 ) 頁： 207-208 2010年8月

高速復元可能な接尾辞配列圧縮法

田中洋輔, 小野廣隆, 定兼邦彦, 山下雅史

電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition) 93 巻 ( 8 ) 頁： 1567-1575 2010年8月

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

大規模文字列データに対する高速な文字列検索は接尾辞配列(SA)を用いて実現できるが,SAには多くの容量が必要になってしまう.SAを圧縮する様々な方法が提案されているが,本論文では出現頻度の高いフレーズの検索が既存の圧縮法に比べて高速な圧縮法を提案する.提案手法では,SAをブロックに分割し,そのブロック内でソートを行い,差分をとったものを保存し,検索時は差分からソート後のSAを取り戻し,区間内をすべて逐次的に検索する.これで検索フレーズのすべての出現位置を得ることができる.実験により,特に検索フレーズの頻度が高い場合,多くの入力データで提案手法の性能が既存の方法より優れていることを示す.

CiNii Research

Local move connectedness of domino tilings with diagonal impurities 査読有り

Nakano Fuminiko, Ono Hirotaka, Sadahiro Taizo

DISCRETE MATHEMATICS 310 巻 ( 13-14 ) 頁： 1918-1931 2010年7月