研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 141 - 160 件目／全件表示 >>

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年

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年

最大支配問題

宮野英次, 小野廣隆

電子情報通信学会技術研究報告. 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の多項式時間アルゴリズムが存在することを示す.

自己安定リーダー選挙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.

木の(<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.

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

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

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

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

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

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

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

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

情報科学技術フォーラム講演論文集 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を取り戻し,区間内をすべて逐次的に検索する.これで検索フレーズのすべての出現位置を得ることができる.実験により,特に検索フレーズの頻度が高い場合,多くの入力データで提案手法の性能が既存の方法より優れていることを示す.

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

Nakano Fuminiko, Ono Hirotaka, Sadahiro Taizo

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

Approximability and inapproximability of the minimum certificate dispersal problem 査読有り

Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

THEORETICAL COMPUTER SCIENCE 411 巻 ( 31-33 ) 頁： 2773-2783 2010年6月

全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)

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

数理解析研究所講究録 1691 巻頁： 155-161 2010年6月

Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)

穂坂祐輔, 小野廣隆, 山下雅史

数理解析研究所講究録 1691 巻頁： 85-90 2010年6月

任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)

野中良哲, 小野廣隆, 山下雅史

数理解析研究所講究録 1691 巻頁： 91-95 2010年6月

不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)

山田陽介, 小野廣隆, 山下雅史

数理解析研究所講究録 1691 巻頁： 148-154 2010年6月

THE SPACE COMPLEXITY OF LEADER ELECTION IN ANONYMOUS NETWORKS 査読有り

Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 21 巻 ( 3 ) 頁： 427-440 2010年6月

The hitting and cover times of Metropolis walks

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi, 小野廣隆

Theoretical Computer Science 411 巻 ( 16 ) 頁： 1889-1894 2010年3月

The hitting and cover times of Metropolis walks 査読有り

Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

THEORETICAL COMPUTER SCIENCE 411 巻 ( 16-18 ) 頁： 1889-1894 2010年3月

全二分木の簡潔な表現

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

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

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

大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた．本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる．提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり，右の子へ巡回するといった操作を定数時間で行うことができる．また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す．To take large-scale data efficiently, succinct data structures that support highspeed operations on compressed data have been developed. In this paper, we focus on full binary trees which are used as patricia tries. We propose for a succinct data structure whose size is n+o(n) bits. This representation enables constant time operations such as traversing from a internal node to its right child node. Then, we show that a suffix tree (ST) is compressible by converting it to a full binary tree.

高頻度なフレーズの検索が高速な索引

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

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

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

大規模データに対する高速な文字列検索は接尾辞配列 (SA) を用いて実現できるが，SA には多くの容量が必要になってしまう．SA を圧縮する様々な方法が提案されているが，提案手法は，SA と転置インデックスを組み合わせることで，出現頻度の高いフレーズの検索が既存の索引に比べ高速な索引を実現する．最終的には実験により，以前提案した別手法5) と似た性能で，ある程度検索時間を調整可能であることを示す．String pattern matching for large-scale data is efficiently achieved by suffix array (SA), but SA requires a large space. Therefore, various methods to compress SA have been proposed. In this paper, we combine SA and Inverted index. As a result, performance of the proposed method is better than existing ones when searching frequent phrases. Experiments show that the proposed method is similar to one which is proposed by us in other times, and able to control search time at some level.

　前のページ - 次のページ　

<小野 廣隆>

論文 - 小野 廣隆

<小野　廣隆>

論文 - 小野　廣隆