研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

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

The (p, q)-total Labeling Problem for Trees 査読有り

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMS AND COMPUTATION, PT 2 6507 巻頁： 49-+ 2010年

Upper and Lower Bounds of Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol 査読有り

Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

PRINCIPLES OF DISTRIBUTED SYSTEMS 6490 巻頁： 491-503 2010年

Pattern Formation through Optimum Matching by Oblivious CORDA Robots 査読有り

Fujinaga Nao, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

PRINCIPLES OF DISTRIBUTED SYSTEMS 6490 巻頁： 1-15 2010年

木のL(2, 1)-ラベリングに対する線形時間アルゴリズム

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

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

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

グラフの k-L(2, 1) -ラベリングとは，頂点への 0 から k までの整数値の割り当てであり，隣接頂点間では少なくとも 2，距離 2 の頂点間では少なくとも 1 の差があるもののことを言う．L(2, 1) -ラベリング問題とは，グラフに対する k-L(2, 1) ラベリングの中で最小の k を求めるものである．この問題は，木幅が 2 のグラフに対してでも NP 困難であることが知られている．一方，多項式時間アルゴリズムは，路や閉路，木といった限られたクラスにしか知られておらず，木に対するアルゴリズムの計算量も 10 年以上 O(Δ4.5n) 時間であった（ただし，Δ はグラフの最大次数，n は木の頂点数）．この計算量は最近になって O(min{n1.75, Δ1.5n}) 時間へと改善されたが，線形時間で解けるかどうかは未解決であった．本論文では，これを解決する木の L(2, 1) -ラベリングに対する線形時間アルゴリズムを提案する．An L(2, 1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f (x)− f (y)| ≥ 2 if x and y are adjacent and |f (x)− f (y)| ≥ 1 if x and y are at distance 2, for all x and y in V(G). A k-L(2, 1)-labeling is an L(2, 1)-labeling f : V(G) → {0, . . . , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ4.5n) for more than a decade, and an O(min{n1.75, Δ1.5n})-time algorithm has appeared recently, where Δ is the maximum degree of T and n = |V(T)|, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem for L(2, 1)-labeling of trees by establishing a linear time algorithm.

1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))

伊藤健洋, 上原隆平, 小野廣隆, 玉木久夫, 宮本裕一郎

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2009 巻頁： 78-79 2009年9月

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

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

THEORETICAL COMPUTER SCIENCE 410 巻 ( 38-40 ) 頁： 3702-3710 2009年9月

RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)

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

情報科学技術フォーラム講演論文集 8 巻 ( 1 ) 頁： 43-50 2009年8月

メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界

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

電子情報通信学会技術研究報告. COMP, コンピュテーション 109 巻 ( 54 ) 頁： 9-12 2009年5月

グラフの最小出次数最大化問題

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

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

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

MAXMINO という無向グラフの向き付け問題の一種について考える．無向枝重みつきグラフの向き付けを与えることにより，重み付き出次数を定義する（枝重みは正整数であるとする）．この問題は，グラフ中の最小重み付き出次数を最大化する問題である．本研究ではまず，MAXMINO は枝重みを {1 , 2} に限定し，かつ各頂点の（重みなし）次数が高々 3，さらにグラフが平面二部であるような場合でも強 NP 困難であり，P= NP でない限り，任意の定数 E ＞ 0 に対して多項式時間では 2 - E 近似不可能であることを示す．次にすべての枝重みが 1 である場合には，多項式時間で解くことができることを示す．これにより，枝重みが wmin よりも大きい枝数が O (log n)であるときにも，多項式時間で解くことができる．さらに，この手法により MAXMINO に対する単純な wmax / wmin 近似多項式時間アルゴリズムを得ることができる（wmax，wmin はそれぞれ枝重みの最大値，最小値)．最後に，入力グラフがカクタスである場合にも MAXMINO は多項式時間で解くことができることを示す．We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 - E for any constant E > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax / wmin -approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph.

連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)

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

数理解析研究所講究録 1649 巻頁： 252-259 2009年5月

2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)

穂坂祐輔, 小野廣隆, 定兼邦彦, 山下雅史

数理解析研究所講究録 1649 巻頁： 203-209 2009年5月

Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)

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

数理解析研究所講究録 1649 巻頁： 160-164 2009年5月

DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths

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

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

証明書分散問題の近似可能性について

泉朋子, 泉泰介, 小野廣隆, 和田幸一

研究報告アルゴリズム（AL） 2009 巻 ( 18 ) 頁： 49-56 2009年2月

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

証明書分散問題(Minimum Certificate Dispersal Problem, MCD)とは，グラフGと要求集合Rが与えられたときに，Rに含まれるすべての要求を満たすよう各ノードにGの辺を割り当て，各ノードに割り当てられる辺の総数を最小化する問題である．要求とはグラフG上の異なる2つのノードの順序対で表され，要求(u, v)を満たすにはノードu, vに割り当てる辺の和集合にGにおけるuからvへの経路が含まれる必要がある．MCDは与えられるグラフが強連結の場合においてもNP-困難であることが既に示されている．本研究では，MCDの近似可能性について議論する．まず，強連結グラフにおいてMCDの近似率の下界がOmega(log n)(nはGのノード数)であることを示し，さらに任意のグラフにおけるMCDに対する多項式時間O(log n)-近似アルゴリズムが構成可能であることを示す．また，既存研究において多項式時間2-近似アルゴリズムであると評価されていたアルゴリズムが，無向グラフを入力とするMCDに対しては多項式時間3/2-近似アルゴリズムであることを示す．Assume that G is a graph and that R is a set of requests which is represented by a reachable ordered pair of nodes in G. The problem discussed in this paper requires us to assign edges to each node such that all requests in R are satisfied and the total number of edges all nodes have is minimized for a given G and R. To satisfy a request (u, v), a set of assigned edges to u and v must contain a path from u to v in G. This problem is called the Minimum Certificate Dispersal problem (MCD) and is NP-hard even if the input graph is restricted to a strongly connected one. In this paper, we consider approximability of MCD. We clarify an optimal approximability / inapproximability bound in terms of order: we prove the approximation ratio of MCD for strongly connected graphs is Omega (log n) and MCD has a polynomial time approximation algorithm whose factor is O(log n) (n is the number of nodes in G). In addition, we prove that when a given graph is restricted to an undirected graph, the MCD algorithm proposed in [11] guarantees 3/2 approximation ratio.

Drawing Borders Efficiently

Iwama Kazuo, Miyano Eiji, Ono Hirotaka, 岩間一雄, 宮野英次, 小野廣隆

Theory of Computing Systems 44 巻 ( 2 ) 頁： 230-244 2009年2月

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

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.

Drawing Borders Efficiently 査読有り

Iwama Kazuo, Miyano Eiji, Ono Hirotaka

THEORY OF COMPUTING SYSTEMS 44 巻 ( 2 ) 頁： 230-244 2009年2月

頻出属性検出階層型ストリームアルゴリズム

溝口隆, 山下雅史, 小野廣隆

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

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

通信ネットワークをノードとエッジと情報源を使って表す.ここで,ノード間の接続は多段階層化されており,根を最上位として,高さiのノード全体を第i層とする.データは情報源から最下位層のノードに対して与えられ,上位層に対しての一方向のみに送られる.ただし,各上位層のあるノードが単位時間当たり受け取ることができる情報の量は最下位層のあるノードが単位時間当たり受け取ることができる量と同じであるとする.本研究はこのような条件と各ノードのメモリを制限した場合に,情報源から得られた全てのデータの中で頻出したデータを最上位のノードが検出するためのストリームアルゴリズムの設計と解析である.

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

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

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

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

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

全二分木の簡潔な表現

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

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

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

検索などに用いる順序木にはLOUDS, BP, DFUDSなどの簡潔表現が提案されている。これらはノード数nの順序木を表現する情報理論的下限2n-Θ(lgn)ビットにかなり近いものである。これらにo(n)ビットの補助データ構造を追加することで定数時間操作をサポートすることができる。簡潔表現としては他にTree Covering(TC)というのも存在する。本発表では順序木の中でもPaCB木などで用いられる全二分木に焦点を当て、これに対する簡潔データ構造を提案する。このデータ構造はDFUDSを基本としてTCを応用している。サイズはn+o(n)ビットとなり全二分木の情報理論的下限に近くなっている。

不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性

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

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

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

ChienとSinclairは, 非協力対称渋滞ゲームにおける分散的なローカルダイナミクスによって, プレイヤー数n, プレイヤーの遷移への動機を制限する係数α, 辺の遅延関数の増加を制限する係数εの多項式回数以下の遷移ステップ数で近似的ナッシュ均衡状態を実現できることを示した.本論文は, その結果を拡張し, 分散的なコスト計算において個々のプレイヤーが他のプレイヤーの戦略についてある種の不完全な情報しか持たない場合にも同様の遷移回数によって必ず遷移を収束させることができる場合があるということを示し, そのために必要十分な条件について考察する.

　前のページ - 次のページ　

<小野 廣隆>

論文 - 小野 廣隆

<小野　廣隆>

論文 - 小野　廣隆