研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 121 - 140 件目／全件表示 >>

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

電子情報通信学会技術研究報告. COMP, コンピュテーション 112 巻 ( 21 ) 頁： 37-43 2012年4月

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

本論文では,ピクセルグリッドから最大重み領域を切り出す問題を扱う.ただし,切り出された領域は,基線に対して基単調図形に分割できなければならない.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 査読有り

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

THEORETICAL COMPUTER SCIENCE 429 巻頁： 144-154 2012年4月

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

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

第74回全国大会講演論文集 2012 巻 ( 1 ) 頁： 269-270 2012年3月

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

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

On the complexity of minimum topic-connected overlay problems

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

全国大会講演論文集 2012 巻 ( 1 ) 頁： 267-269 2012年3月

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

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.

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

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

全国大会講演論文集 2012 巻 ( 1 ) 頁： 269-271 2012年3月

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

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

On the complexity of minimum topic-connected overlay problems

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

第74回全国大会講演論文集 2012 巻 ( 1 ) 頁： 267-268 2012年3月

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

多種ランダムウォークの全訪問時間の上下界

穂坂祐輔, 山内由紀子, 来嶋秀治, 小野廣隆, 山下雅史

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

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

ランダムウォークはインターネットのような巨大なネットワークの探索に有効な手段である．全訪問時間はグラフ上のランダムウォークの重要な指標の一つであり数多くの研究がされている．ネットワークの探索において複数のクローラを使うほうが 1 台のクローラで探索をするよりも速くネットワーク全体を探索できることは明らかである．Alon ら (2011) は k 個のトークンを使う多重ランダムウォークが完全グラフやランダムグラフなどの特定のグラフにおいて 1 台のものよりも k 倍速く全探索できることを示したが，同時にサイクルやパスなどのグラフでは log k 倍にしか高速化できないことも示してる．本研究では k 個のトークンが独立に個々の遷移確率行列に従って遷移する k トークンの多種ランダムウォークを提案する．また単一トークンのランダムウォークにおける Matthews の不等式のように，多種ランダムウォークにおいて全訪問時間の上下界を到達時間から与える不等式を導く．さらに導出した上下界の式が，完全グラフや完全二部グラフ，ランダムグラフにおいてタイトになることを示す．Random walk is a powerful tool for searching a network, especially for a very large network such as the Internet. The cover time is an important measure of a random walk on a finite graph, and has been studied well. For the purpose of searching a network, it is clear that multiple crawlers cover a network faster than a single crawler. Alon et al. (2011) showed that a multiple random walk by k crawlers covers a network k times faster than a single random walk in certain graphs such as complete graphs, random graphs, etc., while the speeding up ratio is limited only to log k times in other graphs such as cycles and paths. This paper investigates a multiplex random walk by k tokens, in which k tokens randomly walks on a graph independently according to an individual transition probability. For the cover time of a multiplex random walk, we present new inequalities similar to celebrated Matthews' inequalities for a single random walk, that provide upper and lower bounds of the cover time by its hitting times. We also show that the bounds are tight in certain graphs, namely complete graphs, bipartite complete graphs, and random graphs.

An Extension of Matthews' Bound to Multiplex Random Walks 査読有り

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

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

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

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

電子情報通信学会技術研究報告. COMP, コンピュテーション 111 巻 ( 360 ) 頁： 37-44 2011年12月

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree 査読有り

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

JOURNAL OF COMBINATORIAL OPTIMIZATION 22 巻 ( 1 ) 頁： 78-96 2011年7月

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

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

数理解析研究所講究録 1744 巻頁： 197-200 2011年6月

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

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

数理解析研究所講究録 1744 巻頁： 60-66 2011年6月

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

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

研究報告アルゴリズム（AL） 2011 巻 ( 4 ) 頁： 1-6 2011年5月

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

本論文では，パターン形成問題と呼ばれる，非同期的に動くロボット群を幾何的な配置に並ばせる問題を考察する．ここでは，各ロボットは各自固有の座標系に従って，他のロボットの配置と目的の配置を観測するできるものとする．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 159 巻 ( 7 ) 頁： 498-508 2011年4月

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree 査読有り

Asahiro Yuichi, Miyano Eiji, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS 159 巻 ( 7 ) 頁： 498-508 2011年4月