Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 161 - 180 of about 236 ／ All the affair displays >>

The (p, q)-total Labeling Problem for Trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

ALGORITHMS AND COMPUTATION, PT 2 Vol. 6507 page： 49-+ 2010

Upper and Lower Bounds of Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol Reviewed

Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

PRINCIPLES OF DISTRIBUTED SYSTEMS Vol. 6490 page： 491-503 2010

Pattern Formation through Optimum Matching by Oblivious CORDA Robots Reviewed

Fujinaga Nao, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

PRINCIPLES OF DISTRIBUTED SYSTEMS Vol. 6490 page： 1-15 2010

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

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

研究報告アルゴリズム（AL） Vol. 2009 ( 7 ) page： 1-8 2009.11

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

グラフの 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))

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

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 Vol. 2009 page： 78-79 2009.9

An O(n(1.75)) algorithm for L(2,1)-labeling of trees Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

THEORETICAL COMPUTER SCIENCE Vol. 410 ( 38-40 ) page： 3702-3710 2009.9

RA-007 Compressing method of Suffix Array whose decoding is fast

Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Vol. 8 ( 1 ) page： 43-50 2009.8

A Tight Upper Bound on the Hitting and the Cover times of Metropolis Walks

NONAKA Yoshiaki, ONO Hirotaka, SADAKANE Hiko, YAMASHITA Masafumi

IEICE technical report Vol. 109 ( 54 ) page： 9-12 2009.5

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

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

研究報告アルゴリズム（AL） Vol. 2009 ( 7 ) page： 1-8 2009.5

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

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に対する最長路長さ分布の計算 (理論計算機科学の深化と応用)

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

数理解析研究所講究録 Vol. 1649 page： 252-259 2009.5

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

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

数理解析研究所講究録 Vol. 1649 page： 203-209 2009.5

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

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

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

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

電子情報通信学会総合大会講演論文集 Vol. 2009 ( 1 ) page： "S-35"-"S-36" 2009.3

On Approximability of the Minimum Certificate Dispersal Problem

IZUMI Tomoko, IZUMI Taisuke, ONO Hirotaka, WADA Koich

IPSJ SIG Notes Vol. 2009 ( 18 ) page： 49-56 2009.2

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

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 Ω(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 Vol. 44 ( 2 ) page： 230-244 2009.2

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

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 Reviewed

Iwama Kazuo, Miyano Eiji, Ono Hirotaka

THEORY OF COMPUTING SYSTEMS Vol. 44 ( 2 ) page： 230-244 2009.2

Hierarchical streaming algorithms for finding freaquent elements

Mizoguchi Ryu, Yamashita Masafumi, Ono Hirotaka

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 62-62 2009

Compressing method of Suffix Array whose decoding is fast

Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 58-58 2009

A Succinct Representation of a Full Binary Tree.

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 59-59 2009

Convergence to Approximate Nash Equilibria in Incomplete Congestion Games

Yamada Yosuke, Ono Hirotaka, Yamashita Masafumi

Record of Joint Conference of Electrical and Electronics Engineers in Kyushu Vol. 2009 ( 0 ) page： 61-61 2009

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka