Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 141 - 160 of about 236 ／ All the affair displays >>

On the Approximability of Minimum Topic Connected Overlay and Its Special Instances Reviewed

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

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011 Vol. 6907 page： 376-387 2011

Approximability of the Path-Distance-Width for AT-free Graphs Reviewed

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

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE Vol. 6986 page： 271-+ 2011

最大支配問題

宮野英次, 小野廣隆

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 110 ( 325 ) page： 53-60 2010.11

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

グラフにおける頂点/辺支配集合問題の新しい亜種について考える.ある頂点はその頂点自身と隣接点を支配すると言い,同様にある辺はその辺自身と隣接する辺を支配すると言う.グラフ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） Vol. 2010 ( 4 ) page： 1-5 2010.11

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

本論文は，自己安定リーダー選挙メディエイテッドポピュレーションプロトコル (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） Vol. 2010 ( 2 ) page： 1-8 2010.11

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

グラフ 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 Convergence of Approximately Nash Transition in Some Incomplete Congestion Games

Yamada Yosuke, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

Vol. 9 ( 1 ) page： 231-232 2010.8

A-022 Approximate String Matching using Suffix Array Compressed

Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Vol. 9 ( 1 ) page： 205-206 2010.8

A-023 Compressing a Suffix Tree by Converting it to a Binary Tree and Using Succinct Data Structures

Baba Masahiro, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Vol. 9 ( 1 ) page： 207-208 2010.8

A Compression Method of Suffix Arrays with Fast Decoding

TANAKA Yosuke, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

The IEICE transactions on information and systems Vol. 93 ( 8 ) page： 1567-1575 2010.8