Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 121 - 140 of about 236 ／ All the affair displays >>

堀山貴史, 伊藤健洋, ガオタントンナスダ, 小野廣隆, 大舘陽太, 徳山豪, 上原隆平, 宇野毅明

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 112 ( 21 ) page： 37-43 2012.4

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

本論文では,ピクセルグリッドから最大重み領域を切り出す問題を扱う.ただし,切り出された領域は,基線に対して基単調図形に分割できなければならない.n×nピクセルグリッドと基線が与えられたとき,この問題はO(n^3)時間で解けることが知られている.これに対し本論文では,ピクセルグリッドのみが与えられたとき,k本の基線を最適に配置することはNP困難であることを示す.さらに,この配置問題に対し,O(n^3)時間の2倍近似アルゴリズムを与える。また,多項式時間で求解できるいくつかのケースや問題の変種も示す.

On the approximability and hardness of minimum topic connected overlay and its special instances Reviewed

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

THEORETICAL COMPUTER SCIENCE Vol. 429 page： 144-154 2012.4

木ネットワークにおける証明書分散問題の近似可能性について

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

第74回全国大会講演論文集 Vol. 2012 ( 1 ) page： 269-270 2012.3

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

証明書分散問題は，与えられた通信要求をセキュアに実現するために各計算機が保有しなければいけない証明書の枚数を最小化する組み合わせ最適化問題である．本研究では，通信要求グラフ，および証明書グラフが木の場合における証明書分散問題の計算困難性について論じる．通信要求グラフが木の場合，その最大次数によって計算困難さが変化すること，および証明書グラフが木の場合は多項式時間で最適解を求めることが可能であることを示す．

On the complexity of minimum topic-connected overlay problems

和田幸一 , JurajHromkovic , 泉泰介 , 小野廣隆 , SteinovaMonika

全国大会講演論文集 Vol. 2012 ( 1 ) page： 267-269 2012.3

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

In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem(Min-TCO, for short) has been investigated:Given a set of t topics and a collection of n users together with the lists of topics they are intersted in, the aim is to collect these users to a network by a minimum number of edges such that every graph induced by users intersted in a common topic is connected.In this paper, we consider the complexity of Min-TCO.

木ネットワークにおける証明書分散問題の近似可能性について

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

全国大会講演論文集 Vol. 2012 ( 1 ) page： 269-271 2012.3

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

証明書分散問題は,与えられた通信要求をセキュアに実現するために各計算機が保有しなければいけない証明書の枚数を最小化する組み合わせ最適化問題である.本研究では,通信要求グラフ,および証明書グラフが木の場合における証明書分散問題の計算困難性について論じる.通信要求グラフが木の場合,その最大次数によって計算困難さが変化すること,および証明書グラフが木の場合は多項式時間で最適解を求めることが可能であることを示す.

On the complexity of minimum topic-connected overlay problems

和田幸一, JurajHromkovic, 泉泰介, 小野廣隆, SteinovaMonika

第74回全国大会講演論文集 Vol. 2012 ( 1 ) page： 267-268 2012.3

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

On cover time bounds of multiplex random walks

Vol. 2012 ( 9 ) page： 1-7 2012.1

An Extension of Matthews' Bound to Multiplex Random Walks Reviewed

Hosaka Yusuke, Yamauchi Yukiko, Kijima Shuji, Ono Hirotaka, Yamashita Masafumi

2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW) page： 872-877 2012

次数上下界制約付きグラフ向き付けにおけるペナルティ最小化

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

電子情報通信学会技術研究報告. COMP, コンピュテーション Vol. 111 ( 360 ) page： 37-44 2011.12

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei

JOURNAL OF COMBINATORIAL OPTIMIZATION Vol. 22 ( 1 ) page： 78-96 2011.7

非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)

藤永直, 小野廣隆, 来嶋秀治, 山下雅史

数理解析研究所講究録 Vol. 1744 page： 197-200 2011.6

Approximating the path-distance-width for κ-cocompmability graphs (計算機科学とアルゴリズムの数理的基礎とその応用--RIMS研究集会報告集)

大舘陽太, 斎藤寿樹, 山中克久, 来嶋秀治, 岡本吉央, 小野廣隆, 宇野裕之, 山崎浩一

数理解析研究所講究録 Vol. 1744 page： 60-66 2011.6

マッチングを用いたパターン形成アルゴリズム

藤永直, 小野廣隆, 来嶋秀治, 山下雅史

研究報告アルゴリズム（AL） Vol. 2011 ( 4 ) page： 1-6 2011.5

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

本論文では，パターン形成問題と呼ばれる，非同期的に動くロボット群を幾何的な配置に並ばせる問題を考察する．ここでは，各ロボットは各自固有の座標系に従って，他のロボットの配置と目的の配置を観測するできるものとする．n 点の座標からなる集合の対 A,B の間のマッチングを求めるアルゴリズム "clockwise matching" を構成し，"clockwise matching" によって任意のパターン形成問題を解くことができることを示す．A geometric pattern formation problem by autonomous mobile robots is investigated in this paper. In the "embedded pattern formation problem" disscussed in this paper, the target pattern is assumed to be visible from the robots via their own (local) coordinate system. We show that our matching algorithm "clockwise matching" which calculates the matching between a pair of patterns A and B both comprising of n coordinates, solves any embedded pattern formation problem.

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Asahiro Yuichi, Miyano Eiji, Ono Hirotaka, 小野廣隆

Discrete Applied Mathematics Vol. 159 ( 7 ) page： 498-508 2011.4

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree Reviewed

Asahiro Yuichi, Miyano Eiji, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS Vol. 159 ( 7 ) page： 498-508 2011.4

GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE Reviewed

Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE Vol. 22 ( 3 ) page： 583-601 2011.4

DS-1-6 On Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol

Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

Proceedings of the IEICE General Conference Vol. 2011 ( 1 ) page： "S-11"-"S-12" 2011.2

Broadcastings and digit tilings on three-dimensional torus networks Reviewed

Okazaki Ryotaro, Ono Hirotaka, Sadahiro Taizo, Yamashita Masafumi

THEORETICAL COMPUTER SCIENCE Vol. 412 ( 4-5 ) page： 307-319 2011.2

Design of Faster Random Walks by Using Topological Information of Graphs

page： 1-5 2011

The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Delta+2 Reviewed

Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

COMBINATORIAL ALGORITHMS Vol. 6460 page： 103-+ 2011

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka