研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 260 件中 181 - 200 件目／全件表示 >>

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.

CiNii Research

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

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

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

CiNii Research

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.

CiNii Research

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 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文) Open Access

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

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

CiNii Research

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

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

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

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

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

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

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

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

数理解析研究所講究録 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.

CiNii Research

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.

DOI： 10.1007/s00224-008-9117-y

CiNii Research

Drawing Borders Efficiently 査読有り

Iwama Kazuo, Miyano Eiji, Ono Hirotaka

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

　前のページ - 次のページ　

<小野 廣隆>

論文 - 小野 廣隆

<小野　廣隆>

論文 - 小野　廣隆