Updated on 2022/10/25

写真a

 
ONO Hirotaka
 
Organization
Graduate School of Informatics Department of Mathematical Informatics 1 Professor
Graduate School
Graduate School of Informatics
Undergraduate School
School of Informatics Department of Natural Informatics
Title
Professor
Contact information
メールアドレス
External link

Degree 1

  1. 博士(情報学) ( 2002.3   京都大学 ) 

Research Interests 30

  1. 確率的解析

  2. 確率的手法

  3. 知識獲得

  4. 省スペース

  5. 文字列検索

  6. 情報検索

  7. 巨大分散システム

  8. 局所情報

  9. 安定性

  10. 列挙アルゴリズム

  11. 分解可能関数

  12. 分子計算

  13. データ解析

  14. データ構造

  15. データ圧縮

  16. データマイニング

  17. ゲノム情報

  18. グラフ探索

  19. オンラインアルゴリズム

  20. エントロピー

  21. 統計力学的手法

  22. 組合せ最適化

  23. 接尾辞配列

  24. ランダムウォー

  25. Web検索

  26. 高度な検索・比較

  27. 頻出集合

  28. 進化ネットワーク

  29. 論理関数

  30. 自己安定システム

Research Areas 4

  1. Informatics / Entertainment and game informatics

  2. Informatics / Mathematical informatics

  3. Informatics / Theory of informatics

  4. Informatics / Information network

Current Research Project and SDGs 1

  1. 資源有効活用と個人効用の向上のための最適化計算技術の開発

Research History 6

  1. Nagoya University   Graduate School of Informatics   Professor

    2017.4

  2. Kyushu University   Associate professor

    2010.9 - 2017.3

  3. King's College London   King's College London   Senior Visiting Researcher

    2010.2 - 2010.9

      More details

    Country:United Kingdom

  4. Kyushu University   Assistant Professor

    2007.4 - 2010.8

  5. Kyushu University   Assistant

    2002.4 - 2007.3

  6. Japan Society for Promotion of Science

    1999.1 - 2002.3

▼display all

Education 3

  1. Kyoto University   Graduate School, Division of Information and Communication   Department of Applied Mathematics and Physics

    1999.4 - 2002.3

      More details

    Country: Japan

  2. Kyoto University   Faculty of Engineering   Applied Mathematics and Physics

    1993.4 - 1997.3

      More details

    Country: Japan

  3. Kyoto University   Graduate school of Engineering   Department of Applied Mathematics and Physics

    1997.4 - 1999.3

Professional Memberships 3

  1. 電子情報通信学会

    2014

  2. 日本オペレーションズ・リサーチ学会

    1998

  3. 情報処理学会

    1996.6

Awards 1

  1. 優秀研究賞

    2020.9   情報科学ワークショップ   L(p, 1) ラベリングのための固定パラメータアルゴリズム

    川井 一馬, 土中 哲秀, 小野 廣隆

 

Papers 193

  1. The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality

    Fukuzono Naoka, Hanaka Tesshu, Kiya Hironori, Ono Hirotaka

    DISCRETE APPLIED MATHEMATICS   Vol. 321   page: 281 - 294   2022.11

     More details

    Language:Japanese   Publisher:Discrete Applied Mathematics  

    The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). It models the diffusion process of information in social networks where several competitive companies want to spread their information, for example. The nature of this game strongly depends on the graph topology, and the relationship is studied from several aspects. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on split graphs, block graphs, and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that a pure Nash equilibrium does not always exist on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

    DOI: 10.1016/j.dam.2022.04.025

    Web of Science

    Scopus

  2. Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants

    Asahiro Y., Jansson J., Lin G., Miyano E., Ono H., Utashima T.

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 223   2022.6

     More details

    Language:Japanese   Publisher:Leibniz International Proceedings in Informatics, LIPIcs  

    The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [2], the Multiset-Restricted Common Subsequence problem (MRCS) [11], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [5, 6]. Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225n)-time, dynamic programming (DP)-based algorithm for RBLCS was proposed [2], where the two input sequences have lengths n and poly(n). We first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422n) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

    DOI: 10.4230/LIPIcs.CPM.2022.15

    Scopus

  3. Capacitated Network Design Games on a Generalized Fair Allocation Model

    Hanaka T., Hirose T., Ono H.

    Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS   Vol. 3   page: 1616 - 1617   2022

     More details

    Language:Japanese   Publisher:Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

    The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge costs and capacities, each agent wants to construct a path from a source to a sink with low cost. The cost of each edge is shared by the users based on a cost-sharing function. One of simple cost-sharing functions is defined as the cost divided by the number of users. It models an ideal setting, where no overhead arises when people share things, though it might be quite rare in real life. In this paper, we model more realistic scenarios of cost-sharing connection games by generalizing the cost-sharing function. The arguments do not depend on specific cost-sharing functions and are applicable for a class of all natural cost-sharing scenarios, which include equal divisions with any natural functional overheads. We show that many bounds of the Price of Anarchy and the Price of Stability under sum-cost and max-cost criteria inherit the no-overhead case.

    Scopus

  4. Computing L(p, 1)-Labeling with Combined Parameters

    Hanaka T., Kawai K., Ono H.

    Journal of Graph Algorithms and Applications   Vol. 26 ( 2 ) page: 241 - 255   2022

     More details

    Language:Japanese   Publisher:Journal of Graph Algorithms and Applications  

    Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices u and v, |f(u) − f(v)| ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e.,maxu∈V (f(u)) − minu∈V (f(u)) + 1). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

    DOI: 10.7155/jgaa.00592

    Scopus

  5. Fair Ride Allocation on a Line

    Amano Y., Igarashi A., Kawase Y., Makino K., Ono H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 13584 LNCS   page: 421 - 435   2022

     More details

    Language:Japanese   Publisher:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This paper extends it to the so-called assignment setting, that is, for multiple facilities and agents, each agent chooses a facility to use and shares the cost with the other agents. Such a situation can be often seen in sharing economy, such as sharing fees for office desks among workers, and taxi fare among customers of possibly different destinations on a line. Our model is regarded as a coalition formation game, based on the fair cost-sharing of the airport problem; we call our model a fair ride allocation on a line. As the criteria of solution concepts, we incorporate Nash stability and envy-freeness into our setting. We show that a Nash-stable feasible allocation that minimizes the social cost of agents can be computed efficiently if a feasible allocation exists. For envy-freeness, we provide several structural properties of envy-free allocations. Based on these, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show the NP-hardness of determining the existence of an allocation under two relaxed envy-free concepts.

    DOI: 10.1007/978-3-031-15714-1_24

    Scopus

  6. Fairness norm through social networks: a simulation approach

    Rifki O., Ono H.

    Computational Social Networks   Vol. 8 ( 1 )   2021.12

     More details

    Language:Japanese   Publisher:Computational Social Networks  

    Recently there has been an increased interest in adopting game-theoretic models to social norms. Most of these approaches are generally lacking a structure linking the local level of the ‘norm’ interaction to its global ‘social’ nature. Although numerous studies examined local-interaction games, where the emphasis is placed on neighborhood relations, regarding social network as a whole unique entity seems to be quite limited. In this paper, we conduct a series of simulation experiments to examine the effects that a network topology could have on the speed of emergence of the social norm. The emphasis is placed on the fairness norm in the ultimatum game context, by considering three network type models (Barabási–Albert, Watts–Strogatz and Erdős–Rényi) and several intrinsic topological properties.

    DOI: 10.1186/s40649-021-00100-4

    Scopus

  7. コンピュテーション研究会 近況報告

    増澤 利光, 小野 廣隆, 安藤 映, 大下 福仁

    情報・システムソサイエティ誌   Vol. 26 ( 2 ) page: 10 - 11   2021.8

     More details

    Language:Japanese   Publisher:一般社団法人電子情報通信学会  

    DOI: 10.1587/ieiceissjournal.26.2_10

    CiNii Research

  8. The computational complexity of the gear placement problem

    HAMA Vitor Mitsuo FUKUSHIGUE, KANAZAWA Shogo, HU Yannan, IMAHORI Shinji, ONO Hirotaka, YAGIURA Mutsunori

    Journal of Advanced Mechanical Design, Systems, and Manufacturing   Vol. 14 ( 5 ) page: JAMDSM0069 - JAMDSM0069   2020

     More details

    Language:English   Publisher:The Japan Society of Mechanical Engineers  

    <p>In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed. The task is to find a placement of a set of gears called sub-gears, to connect every target gear to the torque generator source so that every target gear rotates in a given direction. The objective is to minimize the number of sub-gears to be used. We prove that the GPP is NP-hard by giving a reduction from the Hamiltonian path problem on 3-regular planar graphs, which is known to be NP-complete, to the GPP. We also present an upper bound for the number of sub-gears to be placed.</p>

    DOI: 10.1299/jamdsm.2020jamdsm0069

    Web of Science

    Scopus

    CiNii Research

  9. Hedonic seat arrangement problems

    Bodlaender H.L., Hanaka T., Jaffke L., Ono H., Otachi Y., van der Zanden T.C.

    Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS   Vol. 2020-May   page: 1777 - 1779   2020

     More details

    Language:Japanese   Publisher:Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

    In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on the neighbors in the graph. In this paper, we study the price of stability and fairness in Seat Arrangement, and the computational complexity and the parameterized complexity of finding certain “good” seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement.

    Scopus

  10. Hedonic Seat Arrangement Problems Reviewed International coauthorship

    小野 廣隆

    Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems   Vol. -   page: 1777 - 1779   2020

     More details

  11. Parameterized Complexity of (A, ℓ )-Path Packing. Reviewed

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithmica   Vol. 84 ( 4 ) page: 871 - 895   2022.4

     More details

    Language:Japanese   Publishing type:Research paper (conference, symposium, etc.)  

    DOI: 10.1007/s00453-021-00875-y

    Web of Science

    Scopus

  12. Upper and lower degree-constrained graph orientation with minimum penalty. Reviewed

    Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono

    Theor. Comput. Sci.   Vol. 900   page: 53 - 78   2022.1

     More details

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

    DOI: 10.1016/j.tcs.2021.11.019

    Web of Science

    Scopus

  13. Modeling Imperfect Information TANHINMIN with Structural Oracle Reviewed

    Hironori Kiya, Katsuki Ohto, Hirotaka Ono

    IPSJ Transactions on Mathematical Modeling and Its Applications   Vol. 15 ( 1 ) page: 10 - 17   2022.1

     More details

    Authorship:Last author   Language:English   Publishing type:Research paper (scientific journal)  

    J-GLOBAL

  14. Winner Determination Algorithms for Graph Games with Matching Structures.

    Kanae Yoshiwatari, Hironori Kiya, Tesshu Hanaka, Hirotaka Ono

    IWOCA   Vol. 13270 LNCS   page: 509 - 522   2022

     More details

    Language:Japanese   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1007/978-3-031-06678-8_37

    Scopus

    Other Link: https://dblp.uni-trier.de/db/conf/iwoca/iwoca2022.html#YoshiwatariKHO22

  15. Algorithmic Approach for Combinatorial Game Theory

    Kiya Hironori, Ono Hirotaka

    SYSTEMS, CONTROL AND INFORMATION   Vol. 65 ( 10 ) page: 415 - 420   2021.10

     More details

    Language:Japanese   Publisher:THE INSTITUTE OF SYSTEMS, CONTROL AND INFORMATION ENGINEERS  

    DOI: 10.11509/isciesci.65.10_415

    CiNii Research

  16. Computing the Winner of 2-Player TANHINMIN

    KIYA Hironori, OHTO Katsuki, ONO Hirotaka

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   Vol. E104.A ( 9 ) page: 1134 - 1141   2021.9

     More details

    Authorship:Last author   Language:English   Publishing type:Research paper (scientific journal)   Publisher:The Institute of Electronics, Information and Communication Engineers  

    <p>DAIHINMIN, which means Grand Pauper, is a popular playing-card game in Japan. TANHINMIN is a simplified variant of DAIHINMIN, which was proposed by Nishino in 2007 in order to investigate the mathematical properties of DAIHINMIN. In this paper, we consider a 2-player generalized TANHINMIN, where the deck size is arbitrary <i>n</i>. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.</p>

    DOI: 10.1587/transfun.2020dmp0026

    Web of Science

    Scopus

    CiNii Research

  17. Computing L(p, 1)-Labeling with Combined Parameters Reviewed

    Tesshu Hanaka, Kazuma Kawai, Hirotaka Ono

    WALCOM: Algorithms and Computation   Vol. 12635 LNCS   page: 208 - 220   2021.2

     More details

    Language:Japanese   Publishing type:Part of collection (book)   Publisher:Springer International Publishing  

    DOI: 10.1007/978-3-030-68211-8_17

    Scopus

  18. Graph Orientation with Edge Modifications Reviewed International coauthorship

    Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, T. P. Sandhya

    International Journal of Foundations of Computer Science   Vol. 32 ( 02 ) page: 209 - 233   2021.2

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:World Scientific Pub Co Pte Lt  

    The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph [Formula: see text] of an input undirected graph [Formula: see text] such that either: (Type I) the number of edges in [Formula: see text] is minimized or maximized and [Formula: see text] can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of [Formula: see text] that can be constructed by deleting or inserting a fixed number of edges, [Formula: see text] admits an orientation optimizing some objective involving the vertices’ outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) [Formula: see text]-DEL-MAX, [Formula: see text]-INS-MIN, [Formula: see text]-INS-MAX, and [Formula: see text]-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

    DOI: 10.1142/S012905412150012X

    Web of Science

    Scopus

  19. Reallocation Problems with Minimum Completion Time.

    Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

    CoRR   Vol. abs/2111.02579   2021

     More details

    Publishing type:Research paper (scientific journal)  

    Other Link: https://dblp.uni-trier.de/db/journals/corr/corr2111.html#abs-2111-02579

  20. Graph orientation with splits Reviewed International coauthorship

    Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hesam Nikpey, Hirotaka Ono

    Theoretical Computer Science   Vol. 844   page: 16 - 25   2020.12

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:Elsevier BV  

    DOI: 10.1016/j.tcs.2020.07.013

    Web of Science

    Scopus

  21. Exact algorithms for the repetition-bounded longest common subsequence problem Reviewed International coauthorship

    Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima

    Theoretical Computer Science   Vol. 838   page: 238 - 249   2020.10

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:Elsevier BV  

    DOI: 10.1016/j.tcs.2020.07.042

    Web of Science

    Scopus

  22. Parameterized complexity of independent set reconfiguration problems Reviewed International coauthorship

    Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

    Discrete Applied Mathematics   Vol. 283   page: 336 - 345   2020.9

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:Elsevier BV  

    DOI: 10.1016/j.dam.2020.01.022

    Web of Science

    Scopus

  23. Independent Set Reconfiguration Parameterized by Modular-Width Reviewed

    Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithmica   Vol. 82 ( 9 ) page: 2586 - 2605   2020.9

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:Springer Science and Business Media LLC  

    DOI: 10.1007/s00453-020-00700-y

    Web of Science

    Scopus

    Other Link: http://link.springer.com/article/10.1007/s00453-020-00700-y/fulltext.html

  24. Parameterized Complexity of $$(A,\ell )$$-Path Packing Reviewed International coauthorship

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

    Lecture Notes in Computer Science   Vol. 12126 LNCS   page: 43 - 55   2020.6

     More details

    Language:Japanese   Publishing type:Part of collection (book)   Publisher:Springer International Publishing  

    DOI: 10.1007/978-3-030-48966-3_4

    Scopus

  25. Parameterized Complexity of Safe Set Reviewed International coauthorship

    Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

    Journal of Graph Algorithms and Applications   Vol. 24 ( 3 ) page: 215 - 245   2020.4

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:Journal of Graph Algorithms and Applications  

    DOI: 10.7155/jgaa.00528

    Scopus

  26. Space-Efficient Algorithms for Longest Increasing Subsequence Reviewed International coauthorship

    Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

    Theory of Computing Systems   Vol. 64 ( 3 ) page: 522 - 541   2020.4

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)   Publisher:Springer Science and Business Media LLC  

    DOI: 10.1007/s00224-018-09908-6

    Web of Science

    Scopus

    Other Link: http://link.springer.com/article/10.1007/s00224-018-09908-6/fulltext.html

  27. Hedonic Seat Arrangement Problems. Reviewed International journal

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems     page: 1777 - 1779   2020

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:International Foundation for Autonomous Agents and Multiagent Systems  

    Other Link: https://dblp.uni-trier.de/conf/atal/2020

  28. Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium Reviewed

    Naoka Fukuzono, Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Ryogo Yamaguchi

    SOFSEM 2020: Theory and Practice of Computer Science   Vol. 12011   page: 627 - 635   2020

     More details

    Language:Japanese   Publishing type:Part of collection (book)   Publisher:Springer International Publishing  

    DOI: 10.1007/978-3-030-38919-2_52

    Web of Science

    Scopus

  29. Fair Ride Allocation on a Line.

    Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

    CoRR   Vol. abs/2007.08045   2020

     More details

    Publishing type:Research paper (scientific journal)  

    Other Link: https://dblp.uni-trier.de/db/journals/corr/corr2007.html#abs-2007-08045

  30. A faster parameterized algorithm for PSEUDOFOREST DELETION Reviewed

    Bodlaender Hans L., Ono Hirotaka, Otachi Yota

    DISCRETE APPLIED MATHEMATICS   Vol. 236   page: 42-56   2018.2

     More details

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

    DOI: 10.1016/j.dam.2017.10.018

    Web of Science

  31. Finding environmentally critical transmission sectors, transactions, and paths in global supply chain networks Reviewed

    Hanaka Tesshu, Kagawa Shigemi, Ono Hirotaka, Kanemoto Keiichiro

    ENERGY ECONOMICS   Vol. 68   page: 44-52   2017.10

     More details

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

    DOI: 10.1016/j.eneco.2017.09.012

    Web of Science

  32. Combinatorial Structure Extraction from Large-Scale Data by String Compression

        page: 1-8   2017

     More details

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

  33. Subexponential fixed-parameter algorithms for partial vector domination Reviewed

    Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    DISCRETE OPTIMIZATION   Vol. 22   page: 111-121   2016.11

     More details

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

    DOI: 10.1016/j.disopt.2016.01.003

    Web of Science

  34. The complexity of dominating set reconfiguration Reviewed

    Haddadan Arash, Ito Takehiro, Mouawad Amer E., Nishimura Naomi, Ono Hirotaka, Suzuki Akira, Tebbal Youcef

    THEORETICAL COMPUTER SCIENCE   Vol. 651   page: 37-49   2016.10

     More details

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

    DOI: 10.1016/j.tcs.2016.08.016

    Web of Science

  35. On the Maximum Weight Minimal Separator (コンピュテーション)

    土中 哲秀, Bodlaender Hans L., Zanden T. C. van der, 小野 廣隆

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   Vol. 116 ( 116 ) page: 81-87   2016.6

     More details

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

  36. 情報の窓 2015年秋季シンポジウムルポ(第74回)

    小野 廣隆

    オペレーションズ・リサーチ   Vol. 61 ( 2 ) page: 109-111   2016.2

     More details

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

  37. Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation Reviewed

    Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

    THEORY OF COMPUTING SYSTEMS   Vol. 58 ( 1 ) page: 60-93   2016.1

     More details

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

    DOI: 10.1007/s00224-014-9565-5

    Web of Science

  38. Linear-time algorithm for sliding tokens on trees Reviewed

    Demaine Erik D., Demaine Martin L., Fox-Epstein Eli, Hoang Duc A., Ito Takehiro, Ono Hirotaka, Otachic Yota, Uehara Ryuhei, Yamada Takeshi

    THEORETICAL COMPUTER SCIENCE   Vol. 600   page: 132-142   2015.10

     More details

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

    DOI: 10.1016/j.tcs.2015.07.037

    Web of Science

  39. 2-H-2 IFRS導入の影響に関するCFOアンケート結果からの安定クラスタ抽出(経営)

    大迫 俊輔, 小野 廣隆, 小津 稚加子

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   Vol. 2015   page: 252-253   2015.9

     More details

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

  40. 1-G-3 産業連関ネットワーク解析のための疎化処理と閾値の関係について(公共)

    土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   Vol. 2015   page: 130-131   2015.9

     More details

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

  41. Approximability of minimum certificate dispersal with tree structures Reviewed

    Izumi Taisuke, Izumi Tomoko, Ono Hirotaka, Wada Koichi

    THEORETICAL COMPUTER SCIENCE   Vol. 591   page: 5-14   2015.8

     More details

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

    DOI: 10.1016/j.tcs.2015.01.007

    Web of Science

  42. The searchlight problem for road networks Reviewed

    Dereniowski Dariusz, Ono Hirotaka, Suzuki Ichiro, Wrona Lukasz, Yamashita Masafumi, Zylinski Pawel

    THEORETICAL COMPUTER SCIENCE   Vol. 591   page: 28-59   2015.8

     More details

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

    DOI: 10.1016/j.tcs.2015.04.026

    Web of Science

  43. On the approximability and hardness of minimum topic connected overlay and its special instances (vol 429, pg 144, 2012) Reviewed

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

    THEORETICAL COMPUTER SCIENCE   Vol. 562   page: 660-661   2015.1

     More details

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

    DOI: 10.1016/j.tcs.2014.11.001

    Web of Science

  44. PATTERN FORMATION BY OBLIVIOUS ASYNCHRONOUS MOBILE ROBOTS Reviewed

    Fujinaga Nao, Yamauchi Yukiko, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

    SIAM JOURNAL ON COMPUTING   Vol. 44 ( 3 ) page: 740-785   2015

     More details

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

    DOI: 10.1137/140958682

    Web of Science

  45. Finding All Longest Common Segments in Protein Structures Efficiently Reviewed

    Ng Yen Kaow, Yin Linzhi, Ono Hirotaka, Li Shuai Cheng

    IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS   Vol. 12 ( 3 ) page: 644-655   2015

     More details

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

    DOI: 10.1109/TCBB.2014.2372782

    Web of Science

  46. Reconfiguration of Cliques in a Graph Reviewed

    Ito Takehiro, Ono Hirotaka, Otachi Yota

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015)   Vol. 9076   page: 212-223   2015

     More details

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

    DOI: 10.1007/978-3-319-17142-5_19

    Web of Science

  47. Subgraph Domatic Problem and Writing Capacity of Memory Devices with Restricted State Transitions Reviewed

    Wadayama Tadashi, Izumi Taisuke, Ono Hirotaka

    2015 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)     page: 1307-1311   2015

     More details

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

    Web of Science

  48. 次数制約のあるグラフ有向化問題の計算複雑さについて (回路とシステム)

    朝廣 雄一, ジャンソン ジェスパー, 宮野 英次, 小野 廣隆

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   Vol. 114 ( 312 ) page: 105-112   2014.11

     More details

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

    無向グラフに対するオリエンテーション(グラフ有向化)とは,各辺に対して向き付けを行うことである.オリエンテーションによる結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に,それを次数制約オリエンテーションと呼ぶ.本稿では,次数制約オリエンテーションを求める問題の一種である,2つのお互いに関連するMIN W-LIGHT問題とMAX W-HEAVY問題について考える.任意の固定された非負整数Wに対して,MIN W-LIGHT(またはMAX W-HEAVY)問題は,入力された無向グラフGのオリエンテーションのうち,出次数W以下(またはWP以上)の頂点数を最小化(または最大化)するものを発見することを目的とする.これらの問題の計算複雑さはWの値によって変化する.本稿では,これらの問題の計算複雑さ(主に近似可能性)に関するいくつかの結果を示す.

  49. 次数制約のあるグラフ有向化問題の計算複雑さについて (システム数理と応用)

    朝廣 雄一, ジャンソン ジェスパー, 宮野 英次, 小野 廣隆

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   Vol. 114 ( 313 ) page: 105-112   2014.11

     More details

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

    無向グラフに対するオリエンテーション(グラフ有向化)とは,各辺に対して向き付けを行うことである.オリエンテーションによる結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に,それを次数制約オリエンテーションと呼ぶ.本稿では,次数制約オリエンテーションを求める問題の一種である,2つのお互いに関連するMIN W-LIGHT問題とMAX W-HEAVY問題について考える.任意の固定された非負整数Wに対して,MIN W-LIGHT(またはMAX W-HEAVY)問題は,入力された無向グラフGのオリエンテーションのうち,出次数W以下(またはWP以上)の頂点数を最小化(または最大化)するものを発見することを目的とする.これらの問題の計算複雑さはWの値によって変化する.本稿では,これらの問題の計算複雑さ(主に近似可能性)に関するいくつかの結果を示す.

  50. 次数制約のあるグラフ有向化問題の計算複雑さについて

    朝廣雄一, ジャンソンジェスパー, 宮野英次, 小野廣隆

    研究報告アルゴリズム(AL)   Vol. 2014 ( 19 ) page: 1-8   2014.11

     More details

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

    無向グラフに対するオリエンテーション (グラフ有向化) とは,各辺に対して向き付けを行うことである.オリエンテーションによる結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に,それを次数制約オリエンテーションと呼ぶ.本稿では,次数制約オリエンテーションを求める問題の一種である,2 つのお互いに関連する Min W-Light 問題と Max W-Heavy 問題について考える.任意の固定された非負整数 W に対して,Min W-Light (または Max W-Heavy) 問題は,入力された無向グラフ G のオリエンテーションのうち,出次数 W 以下 (または W 以上) の頂点数を最小化 (または最大化) するものを発見することを目的とする.これらの問題の計算複雑さは W の値によって変化する.本稿では,これらの問題の計算複雑さ (主に近似可能性) に関するいくつかの結果を示す.

  51. Base-object location problems for base-monotone regions Reviewed

    Chun Jinhee, Horiyama Takashi, Ito Takehiro, Kaothanthong Natsuda, Ono Hirotaka, Otachi Yota, Tokuyama Takeshi, Uehara Ryuhei, Uno Takeaki

    THEORETICAL COMPUTER SCIENCE   Vol. 555   page: 71-84   2014.10

     More details

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

    DOI: 10.1016/j.tcs.2013.11.030

    Web of Science

  52. 2-C-3 最大辺支配問題に対する固定パラメータアルゴリズム(離散最適化(4))

    土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   Vol. 2014   page: 198-199   2014.8

     More details

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

  53. 1-H-10 IFRS導入の影響に関するCFOアンケートの因子分析(OR一般)

    大迫 俊輔, 小野 廣隆, 小津 稚加子

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   Vol. 2014   page: 158-159   2014.8

     More details

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

  54. Reconfiguration of list L(2,1)-labelings in a graph Reviewed

    Ito Takehiro, Kawamura Kazuto, Ono Hirotaka, Zhou Xiao

    THEORETICAL COMPUTER SCIENCE   Vol. 544   page: 84-97   2014.8

     More details

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

    DOI: 10.1016/j.tcs.2014.04.011

    Web of Science

  55. Approximating the path-distance-width for AT-free graphs and graphs in related classes Reviewed

    Otachi Yota, Saitoh Toshiki, Yamanaka Katsuhisa, Kijima Shuji, Okamoto Yoshio, Ono Hirotaka, Uno Yushi, Yamazaki Koichi

    DISCRETE APPLIED MATHEMATICS   Vol. 168   page: 69-77   2014.5

     More details

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

    DOI: 10.1016/j.dam.2012.11.015

    Web of Science

  56. Robustness Analysis of Evolutionary Algorithms to Portfolio Optimization Against Errors in Asset Means Reviewed

    Rifki Omar, Ono Hirotaka

    OPERATIONS RESEARCH PROCEEDINGS 2013     page: 369-375   2014

     More details

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

    DOI: 10.1007/978-3-319-07001-8_50

    Web of Science

  57. Depth-First Search Using O(n) Bits Reviewed

    Asano Tetsuo, Izumi Taisuke, Kiyomi Masashi, Konagaya Matsuo, Ono Hirotaka, Otachi Yota, Schweitzer Pascal, Tarui Jun, Uehara Ryuhei

    ALGORITHMS AND COMPUTATION, ISAAC 2014   Vol. 8889   page: 553-564   2014

     More details

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

    DOI: 10.1007/978-3-319-13075-0_44

    Web of Science

  58. (Total) Vector Domination for Graphs with Bounded Branchwidth Reviewed

    Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    LATIN 2014: THEORETICAL INFORMATICS   Vol. 8392   page: 238-249   2014

     More details

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

    Web of Science

  59. Fixed-Parameter Tractability of Token Jumping on Planar Graphs Reviewed

    Ito Takehiro, Kaminski Marcin, Ono Hirotaka

    ALGORITHMS AND COMPUTATION, ISAAC 2014   Vol. 8889   page: 208-219   2014

     More details

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

    DOI: 10.1007/978-3-319-13075-0_17

    Web of Science

  60. Polynomial-Time Algorithm for Sliding Tokens on Trees Reviewed

    Demaine Erik D., Demaine Martin L., Fox-Epstein Eli, Hoang Duc A., Ito Takehiro, Ono Hirotaka, Otachi Yota, Uehara Ryuhei, Yamada Takeshi

    ALGORITHMS AND COMPUTATION, ISAAC 2014   Vol. 8889   page: 389-400   2014

     More details

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

    DOI: 10.1007/978-3-319-13075-0_31

    Web of Science

  61. Approximability of Latin Square Completion-Type Puzzles Reviewed

    Haraguchi Kazuya, Ono Hirotaka

    FUN WITH ALGORITHMS   Vol. 8496   page: 218-229   2014

     More details

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

    Web of Science

  62. On the Parameterized Complexity for Token Jumping on Graphs Reviewed

    Ito Takehiro, Kaminski Marcin, Ono Hirotaka, Suzuki Akira, Uehara Ryuhei, Yamanaka Katsuhisa

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)   Vol. 8402   page: 341-351   2014

     More details

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

    Web of Science

  63. Approximability of graph orientation problems with degree constraints

    ASAHIRO Yuichi, JANSSON Jesper, MIYANO Eiji, ONO Hirotaka

    IEICE technical report. Theoretical foundations of Computing   Vol. 113 ( 371 ) page: 123-130   2013.12

     More details

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

    A degree-constrained graph orientation of an undirected graph is an assignment of a direction to each edge in the graph such that the outdegree of every vertex in the resulting directed graph satisfies a prescribed lower and/or upper bound. Such graph orientations have been studied in many literatures and various characterizations are known. We consider two related optimization problems introduced in [3]: For any fixed non-negative integer W, the problem MAX W-LIGHT (or MIN W-HEAVY) takes as input an undirected graph G and ask for an orientation of G that maximizes (or minimizes) the number of vertices with outdegree at most W (or at least W). The problems' computational complexities vary with W. In this paper we show several results related to their polynomial-time approximability.

  64. グラフの独立点集合遷移問題に対するアルゴリズム

    Demaine Erik D., Demaine Martin L., 伊藤 健洋, 小野 廣隆, 上原 隆平

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   Vol. 113 ( 371 ) page: 7-14   2013.12

     More details

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

    グラフGに対し,|I_b|=|I_r|であるような2つの独立点集合I_bとI_rが与えられたとする.また,Gにおいて,I_bに含まれる各点にはトークンが置かれているとする.スライディングトークン問題とは,I_bからI_rへのGの独立点集合の系列が存在するか判定する問題である.ただし,系列に含まれる各独立点集合は,その1つ前の独立点集合から,ただ1つのトークンをGの辺に沿ってスライドさせることで得られなければならない.この問題は,理想グラフに対してPSPACE完全であることが知られている.本論文では,理想グラフのいくつかの部分クラスに対して,この問題がO(n)時間で解けることを示す.ここで,nはグラフの点数である.また,これらのグラフに対しては,実際にI_bからI_rへ遷移させる最短の系列を多項式時間で見つけることができる.

  65. Optimal approximability of bookmark assignments Reviewed

    Asahiro Yuichi, Miyano Eiji, Murata Toshihide, Ono Hirotaka

    DISCRETE APPLIED MATHEMATICS   Vol. 161 ( 16-17 ) page: 2361-2366   2013.11

     More details

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

    DOI: 10.1016/j.dam.2013.05.018

    Web of Science

  66. A Linear Time Algorithm for L(2,1)-Labeling of Trees Reviewed

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHMICA   Vol. 66 ( 3 ) page: 654-681   2013.7

     More details

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

    DOI: 10.1007/s00453-012-9657-z

    Web of Science

  67. BLOCKSUM is NP-Complete Reviewed

    Haraguchi Kazuya, Ono Hirotaka

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   Vol. E96D ( 3 ) page: 481-488   2013.3

     More details

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

    DOI: 10.1587/transinf.E96.D.481

    Web of Science

  68. Route-Enabling Graph Orientation Problems Reviewed

    Ito Takehiro, Miyamoto Yuichiro, Ono Hirotaka, Tamaki Hisao, Uehara Ryuhei

    ALGORITHMICA   Vol. 65 ( 2 ) page: 317-338   2013.2

     More details

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

    DOI: 10.1007/s00453-011-9589-z

    Web of Science

  69. 太陽熱と非常時対応可能なコージェネレーションによる熱利用システムの導入事例 : 尼崎D.C.グランスクエア (特集 集合住宅の省エネルギー) -- (集合住宅における省エネへの取組み)

    府川 一郎, 中條 広隆, 小野 建

    IBEC   Vol. 33 ( 5 ) page: 40-43   2013.1

     More details

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

  70. Measuring Sensitivity of Evolutionary Algorithms to Errors in Asset Means for Mean-Variance Portfolio Optimization.

    Rifki Omar

    Record of Joint Conference of Electrical and Electronics Engineers in Kyushu   Vol. 2013 ( 0 ) page: 181-182   2013

     More details

    Publishing type:Research paper (scientific journal)  

  71. COALESCING RANDOM WALKS AND VOTING ON CONNECTED GRAPHS Reviewed

    Cooper Colin, Elsaesser Robert, Ono Hirotaka, Radzik Tomasz

    SIAM JOURNAL ON DISCRETE MATHEMATICS   Vol. 27 ( 4 ) page: 1748-1758   2013

     More details

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

    DOI: 10.1137/120900368

    Web of Science

  72. On space complexity of self-stabilizing leader election in mediated population protocol Reviewed

    Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

    DISTRIBUTED COMPUTING   Vol. 25 ( 6 ) page: 451-460   2012.12

     More details

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

    DOI: 10.1007/s00446-012-0173-9

    Web of Science

  73. RA-002 Detecting Network Security Incidents Based on String Compression

    Eto Kouki, Ono Hirotaka, Yamashita Masafumi, Takeuchi Jun'ichi

      Vol. 11 ( 1 ) page: 9-16   2012.9

     More details

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

  74. Deductive Inference for the Interiors and Exteriors of Horn Theories Reviewed

    Makino Kazuhisa, Ono Hirotaka

    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC   Vol. 13 ( 3 )   2012.8

     More details

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

    DOI: 10.1145/2287718.2287723

    Web of Science

  75. ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)

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

    数理解析研究所講究録   Vol. 1799   page: 130-136   2012.6

     More details

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

  76. On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)

    堀山 貴史, 伊藤 健洋, 小野 廣隆, 大舘 陽太, 上原 隆平, 宇野 毅明

    数理解析研究所講究録   Vol. 1799   page: 123-129   2012.6

     More details

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

  77. The (p, q)-total labeling problem for trees Reviewed

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    DISCRETE MATHEMATICS   Vol. 312 ( 8 ) page: 1407-1420   2012.4

     More details

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

    DOI: 10.1016/j.disc.2012.01.007

    Web of Science

  78. 基単調図形に分割可能な最大重み領域を得る基線の配置問題

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

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

     More details

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

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

  79. 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

     More details

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

    DOI: 10.1016/j.tcs.2011.12.033

    Web of Science

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

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

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

     More details

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

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

  81. On the complexity of minimum topic-connected overlay problems

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

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

     More details

    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.

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

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

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

     More details

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

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

  83. On the complexity of minimum topic-connected overlay problems

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

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

     More details

    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.

  84. On cover time bounds of multiplex random walks

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

     More details

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

  85. 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

     More details

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

    DOI: 10.1109/IPDPSW.2012.107

    Web of Science

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

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

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

     More details

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

  87. 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

     More details

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

    DOI: 10.1007/s10878-009-9276-z

    Web of Science

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

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

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

     More details

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

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

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

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

     More details

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

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

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

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

     More details

    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.

  91. 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

     More details

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

  92. 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

     More details

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

    DOI: 10.1016/j.dam.2010.11.003

    Web of Science

  93. 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

     More details

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

    DOI: 10.1142/S0129054111008246

    Web of Science

  94. 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

     More details

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

  95. 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

     More details

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

    DOI: 10.1016/j.tcs.2010.09.028

    Web of Science

  96. Design of Faster Random Walks by Using Topological Information of Graphs

        page: 1-5   2011

     More details

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

  97. 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

     More details

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

    Web of Science

  98. On the Approximability of Minimum Topic Connected Overlay and Its Special Instances Reviewed

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

    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011   Vol. 6907   page: 376-387   2011

     More details

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

    Web of Science

  99. Approximability of the Path-Distance-Width for AT-free Graphs Reviewed

    Otachi Yota, Saitoh Toshiki, Yamanaka Katsuhisa, Kijima Shuji, Okamoto Yoshio, Ono Hirotaka, Uno Yushi, Yamazaki Koichi

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   Vol. 6986   page: 271-+   2011

     More details

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

    Web of Science

  100. 最大支配問題

    宮野 英次, 小野 廣隆

    電子情報通信学会技術研究報告. COMP, コンピュテーション   Vol. 110 ( 325 ) page: 53-60   2010.11

     More details

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

    グラフにおける頂点/辺支配集合問題の新しい亜種について考える.ある頂点はその頂点自身と隣接点を支配すると言い,同様にある辺はその辺自身と隣接する辺を支配すると言う.グラフG=(V,E)と正整数kが与えられたとき,k-頂点(k-辺)支配問題(それぞれ以下k-MaxVD, k-MaxEDと呼ぶ)は高々サイズkの頂点の部分集合D_V&subE;V(D_E&subE;E)の中で,支配する頂点集合(また辺集合)のサイズを最大化するものを求める問題である.本論文では,まずこの問題に対して単純な貪欲アルゴリズムがk-MaxVD, k-MaxEDいずれに対しても近似比(1-1/e)を達成することを示す.次にP≠NPの条件下で,k-MaxVEに対してこの近似比が多項式時間アルゴリズムの最善であることを示す.さらにP≠NPの条件下で,k-MaxEDに対して1303/1304よりも良い近似比の多項式時間アルゴリズムが存在しないことを示す.一方,kがグラフの最小最大マッチングのサイズを超えないという条件下では,k-MaxEDに対して近似比3/4の多項式時間アルゴリズムが存在することを示す.

  101. 自己安定リーダー選挙MPPにおける領域複雑度の上下界について

    溝口 隆, 小野 廣隆, 来嶋 秀治, 山下 雅史

    研究報告アルゴリズム(AL)   Vol. 2010 ( 4 ) page: 1-5   2010.11

     More details

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

    本論文は,自己安定リーダー選挙メディエイテッドポピュレーションプロトコル (SS-LE MPP) の領域複雑度に関する研究結果である.Cai,Izumi and Wada (2009) は n エージェントに対する自己安定リーダー選挙ポピュレーションプロトコル (SS-LE PP) は少なくとも n 個のエージェント状態を必要とすることを示した.さらに n エージェントに対する SS-LE MPP のうちエージェント状態数が n であるプロトコルを与えた.MPP は Chatzigiannakis,Michail and Spirakis (2009) によって紹介された.MPP は分散ネットワークモデルの 1 つで,各エージェント間に局所的なメモリを追加した PP の拡張モデルである.一般的に MPP は PP よりも計算能力が高いことが知られている.一方で SS-LE のエージェント状態に対する空間複雑度の減少可能性については知られていない.本稿では,n エージェントの SS-LE MPP のうちエージェント状態数が n-1 であり,各エージェント間に 1 ビットのメモリが与えられたプロトコルを与える.This paper investigates the space complexity of a self stabilizing leader election in a mediated population protocol (SS-LE MPP). Cai, Izumi and Wada (2009) showed that SS-LE in a population protocol (SS-LE PP) for n agents requires at least n agent-states, and gave a SS-LE PP with n agent-states for n agents. MPP is a model of distributed computation, introduced by Chatzigiannakis, Michail and Spirakis (2009) as an extension of PP allowing an extra memory on every agents pair. While they showed that MPP is stronger than PP in general, it was not known if a MPP can really reduce the space complexity of SS-LE with respect to agent-states. We in this paper give a SS-LE MPP with n - 1 agent-states and a single bit memory on every agents pair for n agents.

  102. 木の(<i>p</i>, <i>q</i>)-全ラベリング問題

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

    研究報告アルゴリズム(AL)   Vol. 2010 ( 2 ) page: 1-8   2010.11

     More details

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

    グラフ G の k-(p,q)-全ラベリングとは,G の節点と辺への 0 から k までの整数値の割当てであり,節点とそれに接続する辺の間では少なくとも p,隣接する 2 節点間または 2 辺間では少なくとも q の差があるもののことをいう.G の (p, q)-全ラベリング数 λTp;q(G) は,k がとりうる値の最小値として定義される.G の (p, q)-全ラベリング問題とは,ラベリング数 λTp;q(G) を求める問題である.本研究では,いくつかのグラフクラスのグラフの (p, q)-全ラベリング数に対して新しい上界と下界を与える.とくに,グラフが木の場合にはタイトな上界と下界を与える.また,グラフが木で p≦3q/2 の場合に (p, q)-全ラベリング問題を解く線形時間アルゴリズムを与え,さらに最大次数が 4 以上という仮定が加わった場合,λTp;q(T) を実現する木Tを完全に特徴づけられることも示す.この結果は,(p; q)-全ラベリング問題の一般化である L (p; q)-ラベリング問題が q が p の約数でないすべての (p; q) の組に対し NP 困難であることと対照的である.A (p,q)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set of nonnegative integers such that |f(x)-f(y)| ≧ p if x is a vertex and y is an edge incident to x, and |f(x)-f(y)| ≧ q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) ∪ E(G). A k-(p,q)-total labeling is a (p,q)-total labeling f:V(G) ∪ E(G) → {0,...,k}, and the (p,q)-total labeling problem asks the minimum k, which we denote by λTp,q(G), among all possible assignments. In this paper, we first give new upper and lower bounds on λTp,q(G) for some classes of graphs G, in particular, tight bounds on λTp,q(T) for trees T. We then show that if p ≦ 3q/2, the problem for trees T is linearly solvable, and give a complete characterization of trees achieving λTp,q(T) if in addition Δ ≧ 4 holds, where Δ is the maximum degree of T. It is contrasting to the fact that the L(p,q)-labeling problem, which is a generalization of the (p,q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p.

  103. A-028 Convergence of Approximately Nash Transition in Some Incomplete Congestion Games

    Yamada Yosuke, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

      Vol. 9 ( 1 ) page: 231-232   2010.8

     More details

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

  104. A-022 Approximate String Matching using Suffix Array Compressed

    Tanaka Yosuke, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

      Vol. 9 ( 1 ) page: 205-206   2010.8

     More details

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

  105. A-023 Compressing a Suffix Tree by Converting it to a Binary Tree and Using Succinct Data Structures

    Baba Masahiro, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

      Vol. 9 ( 1 ) page: 207-208   2010.8

     More details

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

  106. A Compression Method of Suffix Arrays with Fast Decoding

    TANAKA Yosuke, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

    The IEICE transactions on information and systems   Vol. 93 ( 8 ) page: 1567-1575   2010.8

     More details

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

  107. Local move connectedness of domino tilings with diagonal impurities Reviewed

    Nakano Fuminiko, Ono Hirotaka, Sadahiro Taizo

    DISCRETE MATHEMATICS   Vol. 310 ( 13-14 ) page: 1918-1931   2010.7

     More details

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

    DOI: 10.1016/j.disc.2010.02.015

    Web of Science

  108. Approximability and inapproximability of the minimum certificate dispersal problem Reviewed

    Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

    THEORETICAL COMPUTER SCIENCE   Vol. 411 ( 31-33 ) page: 2773-2783   2010.6

     More details

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

    DOI: 10.1016/j.tcs.2010.03.029

    Web of Science

  109. 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)

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

    数理解析研究所講究録   Vol. 1691   page: 155-161   2010.6

     More details

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

  110. Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)

    穂坂 祐輔, 小野 廣隆, 山下 雅史

    数理解析研究所講究録   Vol. 1691   page: 85-90   2010.6

     More details

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

  111. 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)

    野中 良哲, 小野 廣隆, 山下 雅史

    数理解析研究所講究録   Vol. 1691   page: 91-95   2010.6

     More details

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

  112. 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)

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

    数理解析研究所講究録   Vol. 1691   page: 148-154   2010.6

     More details

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

  113. THE SPACE COMPLEXITY OF LEADER ELECTION IN ANONYMOUS NETWORKS Reviewed

    Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   Vol. 21 ( 3 ) page: 427-440   2010.6

     More details

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

    DOI: 10.1142/S0129054110007349

    Web of Science

  114. The hitting and cover times of Metropolis walks

    Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi, 小野 廣隆

    Theoretical Computer Science   Vol. 411 ( 16 ) page: 1889-1894   2010.3

     More details

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

  115. The hitting and cover times of Metropolis walks Reviewed

    Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    THEORETICAL COMPUTER SCIENCE   Vol. 411 ( 16-18 ) page: 1889-1894   2010.3

     More details

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

    DOI: 10.1016/j.tcs.2010.01.032

    Web of Science

  116. A succinct representation of a full binary tree

    BABA MASAHIRO, ONO HIROTAKA, SADAKANE KUNIHIKO, YAMASHITA MASAFUMI

      Vol. 2010 ( 1 ) page: 1-8   2010.2

     More details

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

  117. Index with fast searching in case phrase is frequent

    TANAKA YOSUKE, ONO HIROTAKA, SADAKANE KUNIHIKO, YAMASHITA MASAFUMI

      Vol. 2010 ( 1 ) page: 1-6   2010.1

     More details

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

  118. 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

     More details

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

    Web of Science

  119. 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

     More details

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

    Web of Science

  120. 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

     More details

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

    Web of Science

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

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

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

     More details

    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.

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

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

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

     More details

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

  123. 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

     More details

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

    DOI: 10.1016/j.tcs.2009.04.025

    Web of Science

  124. 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

     More details

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

  125. 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

     More details

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

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

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

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

     More details

    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.

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

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

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

     More details

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

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

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

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

     More details

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

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

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

    数理解析研究所講究録   Vol. 1649   page: 160-164   2009.5

     More details

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

  130. 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

     More details

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

  131. 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

     More details

    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.

  132. Drawing Borders Efficiently

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

    Theory of Computing Systems   Vol. 44 ( 2 ) page: 230-244   2009.2

     More details

    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.

  133. Drawing Borders Efficiently Reviewed

    Iwama Kazuo, Miyano Eiji, Ono Hirotaka

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

     More details

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

    DOI: 10.1007/s00224-008-9117-y

    Web of Science

  134. 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

     More details

    Publishing type:Research paper (scientific journal)  

  135. Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG Reviewed

    Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION   Vol. 5532   page: 98-107   2009

     More details

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

    Web of Science

  136. Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem Reviewed

    Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

    COMPUTING AND COMBINATORICS, PROCEEDINGS   Vol. 5609   page: 56-+   2009

     More details

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

    Web of Science

  137. A Linear Time Algorithm for L(2,1)-Labeling of Trees Reviewed

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHMS - ESA 2009, PROCEEDINGS   Vol. 5757   page: 35-+   2009

     More details

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

    Web of Science

  138. 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

     More details

    Publishing type:Research paper (scientific journal)  

  139. 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

     More details

    Publishing type:Research paper (scientific journal)  

  140. 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

     More details

    Publishing type:Research paper (scientific journal)  

  141. Graph Orientation to Maximize the Minimum Weighted Outdegree Reviewed

    Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

    2009 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-5     page: 1113-+   2009

     More details

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

    Web of Science

  142. How to Design a Linear Cover Time Random Walk on a Finite Graph Reviewed

    Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS   Vol. 5792   page: 104-+   2009

     More details

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

    Web of Science

  143. A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems Reviewed

    Ando Ei, Ono Hirotaka, Yamashita Masafumi

    STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS   Vol. 5792   page: 89-103   2009

     More details

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

    Web of Science

  144. Speeding Up Local-Search Type Algorithms for Designing DNA Sequences under Thermodynamical Constraints Reviewed

    Kawashimo Suguru, Ng Yen Kaow, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   Vol. 5347   page: 168-178   2009

     More details

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

    Web of Science

  145. Route-Enabling Graph Orientation Problems Reviewed

    Ito Takehiro, Miyamoto Yuichiro, Ono Hirotaka, Tamaki Hisao, Uehara Ryuhei

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   Vol. 5878   page: 403-+   2009

     More details

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

    Web of Science

  146. 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees

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

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   Vol. 2008   page: 308-309   2008.9

     More details

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

  147. RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)

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

    情報科学技術フォーラム講演論文集   Vol. 7 ( 1 ) page: 5-6   2008.8

     More details

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

  148. 近傍ハッシュ法によるエラー許容頻出パターン列挙

    橋本 英樹, 小野 廣隆, 宇野 毅明, 漆原 秀子, 柳浦睦憲

    情報処理学会研究報告バイオ情報学(BIO)   Vol. 2008 ( 58 ) page: 63-66   2008.6

     More details

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

    ゲノム配列から,ある機能発現に関わる遺伝子を発見したいという要望がある.このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で頻出する配列パターンの形をとることがしばしばある.本研究では,エラーを含む文字列集合から,ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する.エラーの影響から通常のパターン列挙と異なり,入力文字列には現れないパターンも列挙の対象となる.提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより,高速な全列挙を実現する.We propose a practically fast algorithm that enumerates all m-length substring patterns appearing in at least θ sequences among a given set of string sequences, where at most k errors are allowed for each appearance. The problem of enumerating such substring patterns is derived from the genome science, where frequent substring patterns allowing errors are candidates of a gene related to a certain function. From this context, some pattern should be enumerated even if it does not appear in any sequence, because it may match a sufficient number of sequences by allowing errors. In order to prevent overlooking such potential patterns, we propose a hash-based enumeration algorithm. The algorithm stores not only a substring pattern appearing in a sequence but also its neighboring patterns. By using several techniques/conditions to exclude non-frequent patterns, our algorithm achieves an efficient enumeration of frequent substring patterns allowing errors.

  149. Minimum Weight Balanced Edge Cover Problem

    HARADA Yuta, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

    IPSJ SIG Notes   Vol. 2008 ( 49 ) page: 33-40   2008.5

     More details

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

    For an undirected graph G=(V,E), an edge cover is defined as a set of edges that covers all vertices of V. It is known that a minimum edge cover can be found in polynomial time and forms a collection of star graphs. Previously, the authors of this paper consider the problem of finding a balanced edge cover where the degrees of star center vertices are balanced, and present an O(n^<1/2>m log Δ)-time polynomial time algorithm, where n, m and Δ are the number of vertices, the number of edges and the maximum degree of vertices, respectively. In this paper, for an edge-weighted graph, we consider the problem of finding a minimum weight balanced edge cover, that is, a balanced edge cover in which the total weights of edges is minimized. By characterizing the optimality as the existence of a certain path structure, we develop an O(n^3 m)-time algorithm.

  150. On Necessary Conditions of Linear Cover Time Random Walks

    NONAKA Yoshiaki, ONO Hirotaka, SADAKANE Hiko, YAMASHITA Masafumi

    IEICE technical report   Vol. 108 ( 29 ) page: 33-35   2008.5

     More details

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

    A random walk on a finite graph is a model that a token on a vertex repeatedly moves to an adjacent vertex randomly chosen according to some transition probability. The cover time of a random walk is a criterion of its speed, and roughly speaking, it is the expected number of steps in which the token visits all the vertices. Given a graph, we consider to design a fast random walk in terms of the cover time, by properly setting the transition probability. In this paper, we give necessary conditions for that the given graph has the cover time of O(n), where n is the number of vertices.

  151. 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)

    深見 浩和, 小野 廣隆, 定兼 邦彦, 山下 雅史

    数理解析研究所講究録   Vol. 1599   page: 182-188   2008.5

     More details

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

  152. 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)

    川下 優, 小野 廣隆, 定兼 邦彦, 山下 雅史

    数理解析研究所講究録   Vol. 1599   page: 27-34   2008.5

     More details

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

  153. 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)

    原田 雄太, 小野 廣隆, 定兼 邦彦, 山下 雅史

    数理解析研究所講究録   Vol. 1599   page: 57-64   2008.5

     More details

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

  154. グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)

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

    数理解析研究所講究録   Vol. 1599   page: 73-78   2008.5

     More details

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

  155. 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)

    来見田 裕一, 小野 廣隆, 定兼 邦彦, 山下 雅史

    数理解析研究所講究録   Vol. 1599   page: 127-132   2008.5

     More details

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

  156. 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)

    前村 一哉, 小野 廣隆, 定兼 邦彦, 山下 雅史

    数理解析研究所講究録   Vol. 1599   page: 141-147   2008.5

     More details

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

  157. 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)

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

    数理解析研究所講究録   Vol. 1599   page: 170-175   2008.5

     More details

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

  158. Graph Classes and the Graph Orientation Problem to Minimize the Maximum Weighted Outdegree

    ASAHIRO Yuichi, ONO Hirotaka, MIYANO Eiji

    IPSJ SIG Notes   Vol. 2008 ( 24 ) page: 43-50   2008.3

     More details

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

    Given an undirected graph with edge weights, we are asked to find an orientation, i.e., an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO. As previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tight thresholds of complexity: We show that MMO is (i) in P for cactuses, (ii) weakly NP-hard for multi outerplanar graphs and series-parallel graphs, and also (iii) strongly NP-hard for planar graphs and bipartite graphs.

  159. DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting

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

    電子情報通信学会総合大会講演論文集   Vol. 2008 ( 1 ) page: "S-19"-"S-20"   2008.3

     More details

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

  160. An O(n2) Hitting Time Random Walk Generated by Metropolis Hastings Algorithm

    Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    Record of Joint Conference of Electrical and Electronics Engineers in Kyushu   Vol. 2008 ( 0 ) page: 178-178   2008

     More details

    Publishing type:Research paper (scientific journal)  

  161. Dynamic neighborhood searches for thermodynamically designing DNA sequence Reviewed

    Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   Vol. 4848   page: 130-+   2008

     More details

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

    Web of Science

  162. A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs

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

    情報科学技術フォーラム講演論文集     page: 7-8   2008

     More details

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

  163. The Balanced Edge Cover Problem Reviewed

    Harada Yuta, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   Vol. 5369   page: 246-257   2008

     More details

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

    Web of Science

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

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHM THEORY - SWAT 2008   Vol. 5124   page: 185-+   2008

     More details

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

    Web of Science

  165. The space complexity of the leader election in anonymous networks Reviewed

    Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    2008 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-8     page: 103-110   2008

     More details

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

    Web of Science

  166. Deductive Inference for the Interiors and Exteriors of Horn Theories Reviewed

    Makino Kazuhisa, Ono Hirotaka

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   Vol. 5369   page: 390-+   2008

     More details

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

    Web of Science

  167. 混合ドミノタイリングの連結性

    小野 廣隆, 貞廣 泰造

    電子情報通信学会技術研究報告. COMP, コンピュテーション   Vol. 107 ( 258 ) page: 19-24   2007.10

     More details

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

    正方-八方格子の双対グラフ上の単連結部分グラフにおける完全マッチングについて,局所変形連結性の観点から研究する.これらのグラフは二部性を持たずある意味で不純物を含んでいるため,従来の研究で使われてきた高さ関数を用いた手法を利用することは出来ない.本研究では組合せ的手法を用いて,連結性を保証する最小の局所変形集合を与える:すなわち,これらのグラフ上の任意の完全マッチング同士が,二辺だけを動かす局所変形を繰り返すことにより移りあうことを示す.この結果から完全マッチング全体を状態集合とする簡易なマルコフ連鎖を構成でき,またその定常状態を一様とすることができる.計算シミュレーションでは顕著な統計的性質が観測された.

  168. ホーン理論の内包・外包に対する演繹推論

    牧野 和久, 小野 廣隆

    電子情報通信学会技術研究報告. COMP, コンピュテーション   Vol. 107 ( 127 ) page: 33-39   2007.6

     More details

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

    本論文ではホーン知識ベースの内包・外包に対する演繹推論について考える.知識ベースの内包・外包はその安定性を測るものとして,Makino, Ibaraki [11]により提案された.本論文ではホーン関数(式表現)の内包に対する演繹推論を行う線形時間アルゴリズムを与え,外包に対する演繹推論がco-NP完全であることを示す.またホーン知識がモデル表現で与えられた場合,演繹推論は内包・外包共に計算困難であることを示す.外包のホーン包絡に関しては,モデル表現においては線形時間で解くことができる一方,式表現においてはco-NP完全となることを示す.また各計算困難なクラスにおいて,多項式時間で解ける部分クラスについても議論する.

  169. 負荷分散枝被覆問題に対する最適性とアルゴリズム

    原田 雄太, 小野 廣隆, 定兼 邦彦, 山下 雅史

    電子情報通信学会技術研究報告. COMP, コンピュテーション   Vol. 107 ( 73 ) page: 43-50   2007.5

     More details

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

    無向グラフG=(V,E)において,全ての頂点が少なくとも1つの枝に接しているような枝の集合を枝被覆と呼ぶ.特に最小枝被覆は多項式時間で得られ,またスターグラフの集合により構成されることが知られている.本研究では,各スターの枝数が均等になるような枝被覆を求める負荷分散枝被覆問題を扱う.この問題の応用例として,センサーネットワークの構造最適化などが挙げられる.この目的達成のために,被覆枝における次数に関する狭義単調増加凸関数の和の最小化問題として問題を定式化し,その最適性がある種の交互パスの非存在として特徴付けられることを示す.またこの特徴付けを利用し,最適な枝被覆が最小枝被覆であること,被覆枝における次数列の辞書順が最小となること,最大次数が最小化されることを示す.さらに,この特徴を基にしたO(|V||E|)時間のアルゴリズムを提案する.

  170. On Approximation of Bookmark Assignments

    ASAHIRO Yuichi, MIYANO Eiji, ONO Hirotaka, MURATA Toshihide

    IEICE technical report   Vol. 107 ( 73 ) page: 1-6   2007.5

     More details

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

    Consider a rooted directed acyclic graph G=(V,E)with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor(1-1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than(1-1/e)unless NP&subE;DTIME(N^<o(loglogN)>), where is the size of the inputs.

  171. $k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用)

    坂田 敦, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 269-275   2007.5

     More details

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

  172. 負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用)

    原田 雄太, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 101-108   2007.5

     More details

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

  173. 境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用)

    深見 浩和, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 139-144   2007.5

     More details

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

  174. 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)

    安藤 映, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 202-209   2007.5

     More details

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

  175. ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)

    前村 一哉, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 238-242   2007.5

     More details

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

  176. 部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用)

    後藤 隆元, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 243-249   2007.5

     More details

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

  177. 局所探索法に基づくDNA 配列設計手法(計算機科学の理論とその応用)

    川下 優, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 250-257   2007.5

     More details

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

  178. センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)

    佐薙 光樹, 小野 廣隆, 定兼 邦彦[他]

    数理解析研究所講究録   Vol. 1554   page: 264-268   2007.5

     More details

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

  179. Graph orientation algorithms to minimize the maximum outdegree Reviewed

    Asahiro Yuichi, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   Vol. 18 ( 2 ) page: 197-215   2007.4

     More details

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

    Web of Science

  180. Failure Detectors for Solving k-Set Agreement

    SAKATA Atsushi, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

    IEICE technical report   Vol. 106 ( 566 ) page: 1-6   2007.3

     More details

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

    Failure detectors are distributed oracles that provide each process with information about failures of other processes in distributed systems. It is known that many problems are unsolvable in asynchronous distributed systems if crash failures occur. For such unsolvable problems, failure detectors can be used to make them solvable. How strong information failure detectors should provide, that is, the weakest failure detectors for a certain problem are intensively studied from both theoretical and practical viewpoints. In this paper, we propose two new failure detectors classes, (k-Ω,Σ) and (Ω,Σ_k>), for solving k-Set Agreement problem, where both are generalizations of (Ω,Σ) that is a class of the weakest failure detectors for consensus problem. Furthermore, we consider the reducibility between these failure detector classes and another failure detector class, (Ω^k,Σ), which is also proposed for k-Set Agreement in a related study.

  181. Collecting Moving Objects

    ASAHIRO Yuichi, ONO Hirotaka, MIYANO Eiji, YAMASHITA Masafumi

    The Journal of the Institute of Electronics, Information and Communication Engineers   Vol. 90 ( 3 ) page: 245-247   2007.2

     More details

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

  182. Exploration of Scale-Free Graphs with Degree Information

    Kurumida Yuichi, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    Record of Joint Conference of Electrical and Electronics Engineers in Kyushu   Vol. 2007 ( 0 ) page: 95-95   2007

     More details

    Publishing type:Research paper (scientific journal)  

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

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

    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS   Vol. 4508   page: 167-+   2007

     More details

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

    Web of Science

  184. Approximation Ratio of Algorithms for Constructing Evolutionary Trees from Rooted Triplets

    Maemura Kazuya, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    Record of Joint Conference of Electrical and Electronics Engineers in Kyushu   Vol. 2007 ( 0 ) page: 85-85   2007

     More details

    Publishing type:Research paper (scientific journal)  

  185. Thermodynamically DNA Sequences Design based on Local Search

    Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    Record of Joint Conference of Electrical and Electronics Engineers in Kyushu   Vol. 2007 ( 0 ) page: 93-93   2007

     More details

    Publishing type:Research paper (scientific journal)  

  186. On approximation of bookmark assignments Reviewed

    Asahiro Yuichi, Miyano Eiji, Murata Toshihide, Ono Hirotaka

    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS   Vol. 4708   page: 115-+   2007

     More details

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

    Web of Science

  187. Drawing borders efficiently Reviewed

    Iwama Kazuo, Miyano Eiji, Ono Hirotaka

    FUN WITH ALGORITHMS, PROCEEDINGS   Vol. 4475   page: 213-+   2007

     More details

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

    Web of Science

  188. How to collect balls moving in the Euclidean plane Reviewed

    Asahiro Yuichi, Horiyama Takashi, Makino Kazuhisa, Ono Hirotaka, Sakuma Toshinori, Yamashita Masafumi

    DISCRETE APPLIED MATHEMATICS   Vol. 154 ( 16 ) page: 2247-2262   2006.11

     More details

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

    DOI: 10.1016/j.dam.2006.04.020

    Web of Science

  189. DNA Sequence Design by Dynamic Neighborhood Searches

    KAWASHIMO Suguru, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

    IEICE technical report   Vol. 106 ( 63 ) page: 47-54   2006.5

     More details

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

    In recent years, DNA sequence sets are used in various fields such as nanotechnology and nanocomputing. Since there are several applications using the sequence sets, the sequence sets need to satisfy several constraints depending on the applications. Since several constraints are combinatorial, we consider the sequence sets design problem where the sequence sets are used to solve combinatorial problems. For the purpose, we focus on the overlapping measure which is more combinatorial than other constraints. Then, we propose a local-search based approximation algorithm. To deal with this, we adopt a dynamic neighorhood search frame work, called Variable Neighborhood Search and Variable Depth Search. The computational experiments show that generated sequence sets are as good as the ones generated by exiting methods, or better.

  190. DNA Sequence Desgin Using Hidden Markov Models

    MAEMURA Kazuya, ONO Hirotaka, SADAKANE Kunihiko, YAMASHITA Masafumi

    IEICE technical report   Vol. 106 ( 63 ) page: 39-46   2006.5

     More details

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

    DNA computing is a new computation paradigm to take reaction process of DNA as computation. The design of DNA sequence is a one of crucial research topics in DNA computing. We have to prepare DNA sequences that satisfy many constraints to react DNA as we expected. In our research, we propose sequence design using Hidden Markov Models. Hidden Markov Model is a stochastic model utilizing Markov process. In this paper, as a test of this method, we show experiments and their results of sequence design of DNA whose minimum free energy is small.

  191. DNA sequence design by dynamic neighborhood searches Reviewed

    Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   Vol. 4287   page: 157-+   2006

     More details

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

    Web of Science

  192. Forest search: A paradigm for faster exploration of scale-free networks Reviewed

    Kurumida Yuichi, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    PARALLEL AND DISTRIBUTED PROCESSING AND APPLICATIONS   Vol. 4330   page: 39-+   2006

     More details

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

    Web of Science

  193. A probabilistic model of the DNA conformational change Reviewed

    Shiozaki Masashi, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   Vol. 4287   page: 274-+   2006

     More details

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

    Web of Science

▼display all

MISC 19

  1. Upper and lower bounds on the state-space complexity of Shogi

    都勇志, 木谷裕紀, 小野廣隆

    情報処理学会研究報告(Web)   Vol. 2022 ( GI-47 )   2022

     More details

  2. Stronger Hardness Results on Generalized Puyopuyo

      ( 2021 ) page: 130 - 137   2021.11

     More details

    Language:Japanese  

  3. Sequentially Swapping Colored Tokens on King's Graphs

    Yuto Okada, Hironori Kiya, Yota Otachi, Hirotaka Ono

    SIG Technical Reports   Vol. 2021-GI-46 ( 14 ) page: 1 - 8   2021.6

     More details

    Authorship:Last author   Language:Japanese   Publishing type:Internal/External technical report, pre-print, etc.  

    J-GLOBAL

  4. 個人の性格特性を考慮したソーシャルネットワーク分析

    岩田知旺, 土中哲秀, 小野廣隆

    日本OR学会第48回中部支部研究発表会     2021.3

     More details

    Authorship:Last author   Language:Japanese  

  5. 自動車運搬船における貨物積載プランニングの席割問題に対する数理モデリング

    鵜川知哉, 竹田陽, 三國寛佳, 胡艶楠, 小野廣隆, 柳浦睦憲

    日本OR学会第48回中部支部研究発表会     2021.3

     More details

    Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

  6. パスドミニアリングの必勝判定

    吉渡叶, 木谷裕紀, 小野廣隆

    日本OR学会第48回中部支部研究発表会     2021.3

     More details

    Authorship:Last author   Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

  7. Hedonic Seat Arrangement Problems Invited

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van, der Zanden

        2021.3

     More details

    Language:English   Publishing type:Research paper, summary (national, other academic conference)  

  8. 七並べのグラフ的一般化と必勝判定

    木谷裕紀, 末續鴻輝, 小野廣隆

    2021年 電子情報通信学会 総合大会予稿集   Vol. 2021   2021.3

     More details

    Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

    J-GLOBAL

  9. 一般化費用分配関数の下での容量制約付きネットワーク設計ゲーム

    廣瀬暁之, 土中哲秀, 小野廣隆

    2021年 電子情報通信学会 総合大会予稿集     2021.3

     More details

    Authorship:Last author   Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

  10. 七並べのグラフ的一般化

    木谷 裕紀, 末續 鴻輝, 小野 廣隆

    2020年度 冬のLAシンポジウム     2021.2

     More details

    Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

  11. 重み付き木に対する例外付き準平等分割の計算量

    伊藤 雅士, 宮崎 修一, 中嶋 晋作, 小野 廣隆, 大舘 陽太

    2020年度 冬のLAシンポジウム     2021.2

     More details

    Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

  12. 「組合せゲーム理論」組合せゲームに対するアルゴリズム論的アプローチ

    木谷裕紀, 小野廣隆

    システム/制御/情報   Vol. 65 ( 10 )   2021

     More details

  13. 組合せゲームに対するアルゴリズム論的アプローチ: 「 クミアワセ ゲーム リロン 」 トクシュウゴウ

    キヤ ヒロノリ, オノ ヒロタカ

      Vol. 65 ( 10 ) page: 415 - 420   2021

     More details

    Language:Japanese  

    CiNii Books

  14. Fixed Parameter Algorithms for L(p,1)-labeling

    Kazuma Kawai, Tesshu Hanaka, Hirotaka Ono

      Vol. 120 ( 276 ) page: 30 - 32   2020.12

     More details

    Authorship:Last author   Language:English   Publishing type:Internal/External technical report, pre-print, etc.  

  15. Capacitated Network Design Games on a Generalized Fair Allocation Model

    Toshiyuki Hirose, Tesshu Hanaka, Hirotaka Ono

    AAMAS   Vol. 120 ( 276 ) page: 24 - 27   2020.12

     More details

    Language:English   Publishing type:Internal/External technical report, pre-print, etc.  

    Other Link: https://dl.acm.org/doi/10.5555/3535850.3536053

  16. Capacitated Network Design Games on a Generalized Fair Allocation Model.

    Tesshu Hanaka, Toshiyuki Hirose, Hirotaka Ono

    AAMAS     page: 1616 - 1617   2020.9

     More details

    Authorship:Last author   Language:English   Publishing type:Research paper, summary (national, other academic conference)  

    Other Link: https://dl.acm.org/doi/10.5555/3535850.3536053

  17. L(p, 1) ラベリングのための固定パラメータアルゴリズム

    川井一馬, 土中哲秀, 小野廣隆

    第16回情報科学ワークショップ     2020.9

     More details

    Authorship:Last author   Language:English   Publishing type:Research paper, summary (national, other academic conference)  

  18. 重み付き木の準平等分割の計算量

    伊藤雅士, 小野廣隆

    日本オペレーションズ・リサーチ学会第47回中部支部研究発表会     2020.8

     More details

    Authorship:Last author   Language:Japanese   Publishing type:Research paper, summary (national, other academic conference)  

  19. 不完全情報単貧民に対するオラクルに基づく解析

    木谷裕紀, 大渡勝己, 小野廣隆

    電子情報通信学会大会講演論文集(CD-ROM)   Vol. 2020   2020

     More details

▼display all

Presentations 47

  1. 将棋における状態空間数の上下界

    都 勇志, 木谷 裕紀, 小野 廣隆

    情報処理学会第47回GI研究発表会  2022.3.18 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  2. 将棋における状態空間数の上下界

    都 勇志, 木谷 裕紀, 小野 廣隆

    情報処理学会第47回GI研究発表会  2022.3.18 

     More details

    Event date: 2022.3

  3. 木に対する例外付き準平等分割

    伊藤 雅士, 小野 廣隆, 大舘 陽太

    電子情報通信学会2022年(令和4年)総合大会 COMP学生シンポジウム  2022.3.15 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  4. 辺ケイレス必勝判定アルゴリズムの高速化

    吉渡叶,木谷裕紀,土中哲秀,小野廣隆

    電子情報通信学会2022年(令和4年)総合大会 COMP学生シンポジウム  2022.3.15 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  5. 木に対する例外付き準平等分割

    伊藤 雅士, 小野 廣隆, 大舘 陽太

    電子情報通信学会2022年(令和4年)総合大会 COMP学生シンポジウム  2022.3.15 

     More details

    Event date: 2022.3

  6. 辺ケイレス必勝判定アルゴリズムの高速化

    吉渡叶, 木谷裕紀, 土中哲秀, 小野廣隆

    電子情報通信学会2022年(令和4年)総合大会 COMP学生シンポジウム  2022.3.15 

     More details

    Event date: 2022.3

  7. グラフ上の色付きドロップ順次交換の計算量

    岡田 優斗,木谷 裕紀,大舘 陽太,小野 廣隆

    2021年度 組合せ遷移の学⽣シンポジウム  2022.3.9 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  8. グラフ上の色付きドロップ順次交換の計算量

    岡田 優斗, 木谷 裕紀, 大舘 陽太, 小野 廣隆

    2021年度 組合せ遷移の学?シンポジウム  2022.3.9 

     More details

    Event date: 2022.3

  9. YOMENの解空間サイズとヒント数

    平野巧稀,木谷裕紀,土中哲秀,小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.8 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  10. 色数を制限したぷよぷよの計算困難性について

    江藤宏, 木谷裕紀,小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.7 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  11. グラフ上の色付きドロップ順次交換の計算量

    岡田 優斗,木谷 裕紀,大舘 陽太,小野 廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.7 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  12. グラフマッチング型ゲームに対する必勝判定アルゴリズム

    吉渡叶,木谷裕紀,土中哲秀,小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.7 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  13. YOMENの解空間サイズとヒント数

    平野巧稀, 木谷裕紀, 土中哲秀, 小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.8 

     More details

    Event date: 2022.3

  14. グラフ上の色付きドロップ順次交換の計算量

    岡田 優斗, 木谷 裕紀, 大舘 陽太, 小野 廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.7 

     More details

    Event date: 2022.3

  15. グラフマッチング型ゲームに対する必勝判定アルゴリズム

    吉渡叶, 木谷裕紀, 土中哲秀, 小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.7 

     More details

    Event date: 2022.3

  16. 色数を制限したぷよぷよの計算困難性について

    江藤宏, 木谷裕紀, 小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022.3.7 

     More details

    Event date: 2022.3

  17. 小直径グラフにおけるL(p,q)-ラベリング

    杉山康恭,土中哲秀,小野廣隆

    第49回日本OR学会中部支部研究発表会  2022.3.5 

     More details

    Event date: 2022.3

    Language:Japanese   Presentation type:Oral presentation (general)  

  18. 小直径グラフにおけるL(p,q)-ラベリング

    杉山康恭, 土中哲秀, 小野廣隆

    第49回日本OR学会中部支部研究発表会  2022.3.5 

     More details

    Event date: 2022.3

  19. 辺ケイレスのための指数時間アルゴリズム

    吉渡 叶, 木谷 裕紀, 土中 哲秀, 小野 廣隆

    2021年度 冬のLAシンポジウム  2022.2.3 

     More details

    Event date: 2022.2

    Language:Japanese   Presentation type:Oral presentation (general)  

  20. 木グラフに対する例外付き準平等分割

    伊藤 雅士, 小野 廣隆, 大舘 陽太

    2021年度 冬のLAシンポジウム  2022.2.1 

     More details

    Event date: 2022.2

    Language:Japanese   Presentation type:Oral presentation (general)  

  21. スプリットグラフにおける分数型ヘドニックゲームの安定性の代償

    池山 愛梨, 土中 哲秀, 小野 廣隆

    2021年度 冬のLAシンポジウム  2022.2.2 

     More details

    Event date: 2022.2

    Language:Japanese   Presentation type:Oral presentation (general)  

  22. 最長共通部分列関連問題の多項式時間同値性

    歌島 侃勇, 朝廣 雄一, ジャンソン ジェスパー , リン グオフイ, 宮野 英次, 小野 廣隆

    2021年度 冬のLAシンポジウム  2022.2.2 

     More details

    Event date: 2022.2

    Language:Japanese   Presentation type:Oral presentation (general)  

  23. スプリットグラフにおける分数型ヘドニックゲームの安定性の代償

    池山 愛梨, 土中 哲秀, 小野 廣隆

    2021年度 冬のLAシンポジウム  2022.2.2 

     More details

    Event date: 2022.2

  24. 最長共通部分列関連問題の多項式時間同値性

    歌島 侃勇, 朝廣 雄一, ジャンソン ジェスパー, リン グオフイ, 宮野 英次, 小野 廣隆

    2021年度 冬のLAシンポジウム  2022.2.2 

     More details

    Event date: 2022.2

  25. 木グラフに対する例外付き準平等分割

    伊藤 雅士, 小野 廣隆, 大舘 陽太

    2021年度 冬のLAシンポジウム  2022.2.1 

     More details

    Event date: 2022.2

  26. 辺ケイレスのための指数時間アルゴリズム

    吉渡 叶, 木谷 裕紀, 土中 哲秀, 小野 廣隆

    2021年度 冬のLAシンポジウム  2022.2.3 

     More details

    Event date: 2022.2

  27. 一般化ぷよぷよのより強い計算困難性

    江藤 宏, 木谷 裕紀, 小野 廣隆

    ゲームプログラミングワークショップ2021  2021.11.14 

     More details

    Event date: 2021.11

    Language:Japanese   Presentation type:Oral presentation (general)  

  28. 一般化ぷよぷよのより強い計算困難性

    江藤 宏, 木谷 裕紀, 小野 廣隆

    ゲームプログラミングワークショップ2021  2021.11.14 

     More details

    Event date: 2021.11

  29. Hardness Results on Generalized Puyopuyo International conference

    Hiroshi Eto, Hironori Kiya, Hirotaka Ono

    14th Annual Meeting of the Asian Association for Algorithms and Computation  2021.10.24 

     More details

    Event date: 2021.10

    Language:English   Presentation type:Oral presentation (general)  

  30. Hardness Results on Generalized Puyopuyo

    Hiroshi Eto, Hironori Kiya, Hirotaka Ono

    14th Annual Meeting of the Asian Association for Algorithms and Computation  2021.10.24 

     More details

    Event date: 2021.10

  31. 王将グラフ上での順次交換による色付きドロップ整列の計算量

    岡田 優斗,木谷 裕紀,大舘 陽太,小野 廣隆

    コンピュテーション研究会  2021.10.23 

     More details

    Event date: 2021.10

    Language:Japanese   Presentation type:Oral presentation (general)  

  32. 王将グラフ上での順次交換による色付きドロップ整列の計算量

    岡田 優斗,木谷 裕紀,大舘 陽太,小野 廣隆

    コンピュテーション研究会  2021.10.23 

     More details

    Event date: 2021.10

  33. 頂点被覆を用いた辺ケイレスに対するアルゴリズム

    吉渡 叶, 木谷 裕紀, 土中 哲秀, 小野 廣隆

    関西支部 SSOR 2021   2021.10.16 

     More details

    Event date: 2021.10

    Language:Japanese   Presentation type:Oral presentation (general)  

  34. 頂点被覆を用いた辺ケイレスに対するアルゴリズム

    吉渡 叶, 木谷 裕紀, 土中 哲秀, 小野 廣隆

    関西支部 SSOR 2021  2021.10.16 

     More details

    Event date: 2021.10

  35. 重み付き木に対する例外付き準平等分割の計算量

    伊藤 雅士, 宮崎 修一, 小野 廣隆, 大舘 陽太

    第17回 情報科学ワークショップ  2021.9.13 

     More details

    Event date: 2021.9

    Language:Japanese   Presentation type:Oral presentation (general)  

  36. ブロックスプリットグラフにおける分数型ヘドニックゲームの安定性の代償

    池山愛梨, 土中哲秀, 小野廣隆

    第17回 情報科学ワークショップ  2021.9.12 

     More details

    Event date: 2021.9

    Language:Japanese   Presentation type:Oral presentation (general)  

  37. 辺ケイレスに対する指数時間必勝判定アルゴリズム

    吉渡 叶, 木谷 裕紀, 土中 哲秀, 小野 廣隆

    第17回 情報科学ワークショップ  2021.9.12 

     More details

    Event date: 2021.9

    Language:Japanese   Presentation type:Oral presentation (general)  

  38. トリオ支配集合問題に対する固定パラメータアルゴリズム

    宇田 冴輝, 土中 哲秀, 大舘 陽太, 小野 廣隆

    第17回 情報科学ワークショップ  2021.9.13 

     More details

    Event date: 2021.9

    Language:Japanese   Presentation type:Oral presentation (general)  

  39. トリオ支配集合問題に対する固定パラメータアルゴリズム

    宇田 冴輝, 土中 哲秀, 大舘 陽太, 小野 廣隆

    第17回 情報科学ワークショップ  2021.9.13 

     More details

    Event date: 2021.9

  40. ブロックスプリットグラフにおける分数型ヘドニックゲームの安定性の代償

    池山愛梨, 土中哲秀, 小野廣隆

    第17回 情報科学ワークショップ  2021.9.12 

     More details

    Event date: 2021.9

  41. 辺ケイレスに対する指数時間必勝判定アルゴリズム

    吉渡 叶, 木谷 裕紀, 土中 哲秀, 小野 廣隆

    第17回 情報科学ワークショップ  2021.9.12 

     More details

    Event date: 2021.9

  42. 重み付き木に対する例外付き準平等分割の計算量

    伊藤 雅士, 宮崎 修一, 小野 廣隆, 大舘 陽太

    第17回 情報科学ワークショップ  2021.9.13 

     More details

    Event date: 2021.9

  43. Multi-player open-hand BABANUKI

    Hironori Kiya, Hirotaka Ono

    The 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCG3 2020+1)  2021.9.3 

     More details

    Event date: 2021.9

  44. Multi-player open-hand BABANUKI International conference

    Hironori Kiya, Hirotaka Ono

    The 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCG3 2020+1)  2021.9.3 

     More details

    Event date: 2021.9

    Language:English   Presentation type:Oral presentation (general)  

  45. 王将グラフ上での順次交換による色付きドロップ整列の計算量

    岡田 優斗,木谷 裕紀,大舘 陽太,小野 廣隆

    情報処理学会第46回GI研究発表会  2021.6.20 

     More details

    Event date: 2021.6

    Language:Japanese   Presentation type:Oral presentation (general)  

  46. 一般化費用分配モデル下での容量制約付きネットワーク設計ゲーム

    廣瀬 暁之, 土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会 九州支部 若手OR研究交流会 2020  2020.11.28 

     More details

    Event date: 2020.11

    Language:Japanese   Presentation type:Oral presentation (general)  

  47. ペア支配集合の頂点被覆によるパラメータ化アルゴリズム

    宇田 冴輝, 土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会 九州支部 若手OR研究交流会 2020  2020.11.28 

     More details

    Language:Japanese   Presentation type:Oral presentation (general)  

▼display all

KAKENHI (Grants-in-Aid for Scientific Research) 7

  1. 超スマート社会時代のアルゴリズム工学 - パラメータ化近似均衡計算

    Grant number:22H00513  2022.4 - 2027.3

    科学研究費助成事業  基盤研究(A)

    小野 廣隆, 柳浦 睦憲, 大舘 陽太, 脊戸 和寿, 土中 哲秀

      More details

    Authorship:Principal investigator 

    Grant amount:\40820000 ( Direct Cost: \31400000 、 Indirect Cost:\9420000 )

    均衡解は多主体最適化系における安定解であり,超スマート社会における混雑・衝突の予測・制御における鍵となる概念である.本研究では,これまで最適解発見を主な対象としていたアルゴリズム設計論の対象を均衡解発見へと発展・拡大する.通常の最適化がNP, coNPに属するのに対し均衡発見はΣ2, Π2といった多項式階層におけるより上位の計算量クラス,あるいは近傍探索におけるPLS, PPADといった計算クラスに属するため,従来型の最適化研究を超えた新たな計算量理論の展開が必要となる.本研究では,超スマート社会における基盤技術を提供する,パラメータ化計算量に基づく新たなアルゴリズム工学の確立を目指す.

  2. 最適化計算型クエリーのためのプリプロセッシングアルゴリズム論

    Grant number:21K19765  2021.7 - 2024.3

    科学研究費助成事業  挑戦的研究(萌芽)

    小野 廣隆

      More details

    Authorship:Principal investigator 

    Grant amount:\6110000 ( Direct Cost: \4700000 、 Indirect Cost:\1410000 )

    本研究では最適化計算型クエリー+プリプロセッシングのための新たなアルゴリズム論を展開する.最適化計算型クエリーのプリプロセッシングには,付加する補助情報の量と最適化自体の計算量の関係, プリプロセッシングに要する計算量と最適化自体の計算量の関係等,各種のトレードオフ関係が存在する.これは個別に研究されてきたアルゴリズム理論上の諸問題が最適化計算型クエリーに対するプリプロセッシングという設定で融合することを意味する.本研究はこの新しい計算スキームにおける汎用的なアプローチを構築,各種のトレードオフ関係の評価体系の提案をするとともに,実装・評価を通した新たなアルゴリズム設計論の展開に挑戦する.

  3. アルゴリズム基礎理論の追究・発展 International coauthorship

    Grant number:20H05967  2020.11 - 2025.3

    日本学術振興会  科学研究費助成事業 学術変革領域研究(A)  学術変革領域研究(A)

    牧野 和久, 小野 廣隆, 定兼 邦彦, 河村 彰星, 玉置 卓, 瀧本 英二, 渋谷 哲朗, 小野 廣隆, 定兼 邦彦, 河村 彰星, 玉置 卓, 瀧本 英二, 渋谷 哲朗

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

    Grant amount:\260000 ( Direct Cost: \200000 、 Indirect Cost:\60000 )

    本研究では,現在の高度情報化社会を駆動する「アルゴリズム」の基礎理論をさらに追及し,展開させること目的とする.P vs NP問題に代表されるように,アルゴリズム分野において未解決に残された部分は数多く存在する.一方,情報学,工学,農学,医学など多様な応用分野では,それぞれに特化したアルゴリズムが開発されている.それらアルゴリズムを飛躍的に進化させるためには,基礎理論の革新が必要不可欠な現状にある.
    本研究では,データ構造効率化法,離散構造解析法を行うこと,また,他の計画班と密接に連携を行うことで,アルゴリズム理論の革新を行う.

  4. 消費行動分析・効率性分析・サプライチェーン分析を統合した二酸化炭素排出評価

    Grant number:20H00081  2020.4 - 2025.3

    日本学術振興会  科学研究費助成事業 基盤研究(A)  基盤研究(A)

    加河 茂美, 小野 廣隆, 藤井 秀道, 稗貫 峻一, 後藤 美香, 永島 史弥, 馬奈木 俊介, 近藤 康之, 南齋 規介, 小野 廣隆, 藤井 秀道, 稗貫 峻一, 後藤 美香, 永島 史弥, 馬奈木 俊介, 近藤 康之, 南齋 規介

      More details

    Authorship:Coinvestigator(s) 

    第一の課題では、自動車の動的離散選択モデルの推定を行い、需要政策が自動車の最終需要に付随するライフサイクルCO2排出量に与える影響を推計し、需要政策が温暖化緩和に果たす役割を定量的に明らかにする。第二の研究課題では、日本の自動車製造に不可欠な金属14部門に着目したサプライチェーンDEAを行い、金属生産の技術効率・サプライチェーン効率の向上が自動車の最終需要に付随するCO2排出量に与える影響を分析する。第三の研究課題では、第一と第二の課題で明らかになる自動車需要政策に伴う最終需要変化と金属部門の効率性向上に伴う投入変化を考慮したサプライチェーンネットワーク分析を行う。

  5. Analysis of unbounded scheduling problems

    Grant number:17K19960  2017.6 - 2021.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Research (Exploratory)  Grant-in-Aid for Challenging Research (Exploratory)

      More details

    Authorship:Coinvestigator(s) 

  6. 局所探索型計算のパラメータ化計算量理論

    Grant number:17H01698  2017.4 - 2021.3

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    小野 廣隆, 柳浦 睦憲, 柳浦 睦憲

      More details

    Authorship:Principal investigator 

    Grant amount:\9620000 ( Direct Cost: \7400000 、 Indirect Cost:\2220000 )

    遺伝的アルゴリズム,タブー探索,アニーリングといった計算困難な組合せ最適化問題に対するメタ解法(メタ戦略)は,設計が比較的簡単であり,また実用的には十分な近似精度が得られることが知られている反面,理論的な精度の保障に成功している例は限られている.このためメタ解法の高速化や高精度化に関する研究には職人芸的なものが多いのが現状である.本研究はこれらメタ解法に共通する基本操作である局所探索・局所変形に対し新たにパラメータ化計算の視点を導入し,アルゴリズム設計論・性能分析論を構築する.メタ戦略の高速化・高精度化の非自明性の一つは,局所探索・局所変形の「性能」は近傍系の大きさに依存し,近傍の大きさと探索のための計算量はトレードオフの関係にある.このトレードオフ関係をパラメータ化計算の観点から分析し,局所探索型アルゴリズムのための新たなアルゴリズム設計論・計算論を展開する.
    <BR>
    前年度は有向グラフにおける最適化問題のパラメータ化計算量解明,グラフの擬森化のパラメータ化計算量, 最長増加部分列に対する領域効率のよいアルゴリズム(部分列長がパラメータ)について研究を行い,それぞれの派生問題に対し固定パラメータアルゴリズムの設計可能性や,実際の設計を行ったが,H30年度はこれらを局所探索に展開すべく,グラフ分割問題(ヘドニックゲームを含む),グラフラベリング問題等に対する局所探索に関する計算量に関して考察した.特にグラフ分割(ヘドニックゲーム)のある典型モデルは,次数がある定数以下であったとしてもPLS完全であることがわかるなどの結果が得られた.特にヘドニックゲームなどのエージェント型最適化問題の各エージェントの行動は局所探索アルゴリズムの動作とみなすこともできるため,これらの問題に対する近傍複雑度の研究に次年度以降重点を置くことを考えている.

  7. Combinatorial Optimization

      More details

    Grant type:Competitive

▼display all

 

Teaching Experience (Off-campus) 2

  1. 微分積分学II

    2017.10

  2. 微分積分学I

    2017.4

 

Social Contribution 1

  1. 『数学セミナー』での記事掲載

    Role(s):Contribution

    日本評論社  2020.10

Academic Activities 11

  1. 電子情報通信学会コンピュテーション研究会 副委員長

    Role(s):Planning, management, etc., Panel moderator, session chair, etc.

    2020.5 - 2022.4

     More details

    Type:Academic society, research group, etc. 

  2. The Ninth International Symposium on Computing and Networking (CANDAR2021), Program Committee

    Role(s):Planning, management, etc.

    2021.11

     More details

    Type:Competition, symposium, etc. 

  3. 第33回 RAMP数理最適化シンポジウム・プログラム委員(セッションオーガナイザー)

    Role(s):Planning, management, etc., Panel moderator, session chair, etc.

    日本オペレーションズ・リサーチ学会  2021 - 2021.11

     More details

    Type:Competition, symposium, etc. 

  4. The 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCG3 2020+1), Program Committee

    Role(s):Planning, management, etc.

    2021 - 2021.9

     More details

    Type:Competition, symposium, etc. 

  5. 日本オペレーションズリサーチ学会中部支部 運営委員

    Role(s):Planning, management, etc.

    2020.3 - 2022.2

     More details

    Type:Academic society, research group, etc. 

  6. 12th International Conference on Algorithms and Complexity, CIAC2021, program committee

    Role(s):Planning, management, etc.

    2020 - 2021.5

     More details

    Type:Competition, symposium, etc. 

  7. The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21), Program committee

    Role(s):Planning, management, etc.

    2020 - 2021.2

     More details

    Type:Competition, symposium, etc. 

  8. The 23rd IEEE International Conference on Computational Science and Engineering (CSE 2020) ,Program Committee

    Role(s):Planning, management, etc.

    2020 - 2021.1

     More details

    Type:Competition, symposium, etc. 

  9. 18th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA2020, program comittee

    Role(s):Planning, management, etc.

    2020 - 2020.12

     More details

    Type:Competition, symposium, etc. 

  10. The 23rd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020, program committee

    Role(s):Planning, management, etc.

    2020 - 2020.11

     More details

    Type:Competition, symposium, etc. 

  11. The Eighth International Symposium on Computing and Networking, CANDAR2020, program committee

    Role(s):Planning, management, etc.

    2020 - 2020.11

     More details

    Type:Competition, symposium, etc. 

▼display all