2024/10/18 更新

写真a

オノ ヒロタカ
小野 廣隆
ONO Hirotaka
所属
大学院情報学研究科 数理情報学専攻 数理情報基礎論 教授
大学院担当
大学院情報学研究科
学部担当
情報学部 自然情報学科
職名
教授
連絡先
メールアドレス
外部リンク

学位 1

  1. 博士(情報学) ( 2002年3月   京都大学 ) 

研究キーワード 30

  1. 組合せ最適化

  2. 接尾辞配列

  3. ランダムウォー

  4. Web検索

  5. 高度な検索・比較

  6. 頻出集合

  7. 進化ネットワーク

  8. 論理関数

  9. 自己安定システム

  10. 統計力学的手法

  11. 確率的解析

  12. 確率的手法

  13. 知識獲得

  14. 省スペース

  15. 文字列検索

  16. 情報検索

  17. 巨大分散システム

  18. 局所情報

  19. 安定性

  20. 列挙アルゴリズム

  21. 分解可能関数

  22. 分子計算

  23. データ解析

  24. データ構造

  25. データ圧縮

  26. データマイニング

  27. ゲノム情報

  28. グラフ探索

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

  30. エントロピー

研究分野 5

  1. 情報通信 / エンタテインメント、ゲーム情報学

  2. 情報通信 / 数理情報学

  3. 情報通信 / 情報学基礎論

  4. 情報通信 / 情報ネットワーク

  5. 情報通信 / 計算機システム

現在の研究課題とSDGs 1

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

経歴 6

  1. 九州大学   大学院経済学研究院   准教授

    2010年9月 - 2017年3月

  2. 名古屋大学   情報学研究科   教授

    2017年4月 - 現在

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

    2010年2月 - 2010年9月

      詳細を見る

    国名:グレートブリテン・北アイルランド連合王国(英国)

  4. 九州大学   大学院システム情報科学研究院   助教

    2007年4月 - 2010年8月

  5. 九州大学   大学院システム情報科学研究院   助手

    2002年4月 - 2007年3月

  6. 日本学術振興会   特別研究員(DC2)

    1999年1月 - 2002年3月

▼全件表示

学歴 7

  1. 京都大学   情報学研究科   数理工学専攻

    1999年4月 - 2002年3月

      詳細を見る

    国名: 日本国

  2. 京都大学   工学部   数理工学科

    1993年4月 - 1997年3月

      詳細を見る

    国名: 日本国

  3. 京都大学

    - 2002年

  4. 京都大学   情報学研究科   数理工学専攻

    - 2002年

      詳細を見る

    国名: 日本国

  5. 京都大学   大学院工学研究科   数理工学専攻

    1997年4月 - 1999年3月

  6. 京都大学

    - 1997年

  7. 京都大学   工学部   数理工学科

    - 1997年

      詳細を見る

    国名: 日本国

▼全件表示

所属学協会 3

  1. 電子情報通信学会

    2014年 - 現在

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

    1998年 - 現在

  3. 情報処理学会

    1996年6月

受賞 7

  1. Best Paper Award

    2024年3月   The Program Committee of The 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024   Structural Parameterizations of Vertex Integrity

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otach

  2. Best Paper Award

    2024年2月   The Program Committee of The 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024)  

    Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono, Kanae Yoshiwatari

  3. 優秀研究賞

    2023年9月   第19回情報科学ワークショップ実行委員会   離合コスト下のパス計画ゲームの計算量

    関口裕也, 土中哲秀, 小野廣隆

  4. 25th Workshop on Advances in Parallel and Distributed Computational Models. Outstanding Paper Award

    2023年5月   APDCM2023 Program Committees   Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

    Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

  5. The 28th International Computing and Combinatorics Conference, Best Paper Candidate

    2022年10月   Reallocation Problems with Minimum Completion Time

    Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

  6. 優秀研究賞

    2022年9月   第18回情報科学ワークショップ実行委員会   (色付き)辺ケイレスの計算量

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

  7. 優秀研究賞

    2020年9月   第16回 情報科学ワークショップ実行委員会   L(p, 1) ラベリングのための固定パラメータアルゴリズム

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

▼全件表示

 

論文 226

  1. Polynomial-time equivalences and refined algorithms for longest common subsequence variants

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

    Discrete Applied Mathematics   353 巻   頁: 44 - 64   2024年8月

     詳細を見る

    出版者・発行元:Discrete Applied Mathematics  

    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 article, we study four variants of LCS: the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (RBLCS), the MULTISET-RESTRICTED COMMON SUBSEQUENCE problem (MRCS), the TWO-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (2FLCS), and the ONE-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (1FLCS). 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, where the two input sequences have lengths n and poly(n). Here, 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.1016/j.dam.2024.04.006

    Scopus

  2. Grouped domination parameterized by vertex cover, twin cover, and beyond

    Hanaka, T; Ono, H; Otachi, Y; Uda, S

    THEORETICAL COMPUTER SCIENCE   996 巻   2024年5月

     詳細を見る

    出版者・発行元:Theoretical Computer Science  

    A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S1,S2,…,Sk such that the size of each unit Si is r and the subgraph of G induced by Si is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets (r=1), paired dominating sets (r=2), and connected dominating sets (r is arbitrary and k=1). In this paper, we investigate the computational complexity of r-GROUPED DOMINATING SET, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r-GROUPED DOMINATING SET is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r-GROUPED DOMINATING SET for every fixed r>0 is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r-GROUPED DOMINATING SET is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic (MSO2). This fixed-parameter tractability is good news, but the running time is not practical. We then design an O⁎(min⁡{(2τ(r+1))τ,(2τ)2τ})-time algorithm for general r≥2, where τ is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., r∈{2,3}, we can speed up the algorithm, whose running time becomes O⁎((r+1)τ). We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r-GROUPED DOMINATING SET.

    DOI: 10.1016/j.tcs.2024.114507

    Web of Science

    Scopus

  3. Safe sets and in-dominating sets in digraphs

    Bai, YD; Bang-Jensen, J; Fujita, S; Ono, H; Yeo, AD

    DISCRETE APPLIED MATHEMATICS   346 巻   頁: 215 - 227   2024年3月

     詳細を見る

    出版者・発行元:Discrete Applied Mathematics  

    A non-empty subset S of the vertices of a digraph D is a safe set if (i) for every strongly connected component M of D−S, there exists a strongly connected component N of D[S] such that there exists an arc from M to N; and (ii) for every strongly connected component M of D−S and every strongly connected component N of D[S], we have |M|≤|N| whenever there exists an arc from M to N. In the case of acyclic digraphs a set X of vertices is a safe set precisely when X is an in-dominating set, that is, every vertex not in X has at least one arc to X. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant c, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on n vertices in which no strong component has size more than clog(n). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every ϵ>0 there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most log1+ϵ(n). We also discuss bounds on the cardinality of safe sets in tournaments.

    DOI: 10.1016/j.dam.2023.12.012

    Web of Science

    Scopus

  4. Winner Determination Algorithms for Graph Games with Matching Structures

    Hanaka, T; Kiya, H; Ono, H; Yoshiwatari, K

    ALGORITHMICA   86 巻 ( 3 ) 頁: 808 - 824   2024年3月

     詳細を見る

    掲載種別:研究論文(学術雑誌)   出版者・発行元:Algorithmica  

    Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, while gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in O∗(2n) time by a simple algorithm, where n is the order of the input graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O∗(1.4143τ2+3.17τ), O∗(1.3161τ2+4τ), and O∗(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O∗((n/ν+1)ν)-time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O∗(2n/2)(=O(1.4143n)) time, which improves O∗(3n/3)(=O(1.4423n)) by a direct adjustment of the analysis of Bodlaender et al.’s O∗(3n/3)-time algorithm for Node Kayles.

    DOI: 10.1007/s00453-023-01136-w

    Web of Science

    Scopus

  5. Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover

    Horiyama T., Kobayashi Y., Ono H., Seto K., Suzuki R.

    Proceedings of the AAAI Conference on Artificial Intelligence   38 巻 ( 18 ) 頁: 20726 - 20734   2024年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Proceedings of the AAAI Conference on Artificial Intelligence  

    The uniqueness of an optimal solution to a combinatorial optimization problem attracts many fields of researchers’ attention because it has a wide range of applications, it is related to important classes in computational complexity, and an instance with only one solution is often critical for algorithm designs in theory. However, as the authors know, there is no major benchmark set consisting of only instances with unique solutions, and no algorithm generating instances with unique solutions is known; a systematic approach to getting a problem instance guaranteed having a unique solution would be helpful. A possible approach is as follows: Given a problem instance, we specify a small part of a solution in advance so that only one optimal solution meets the specification. This paper formulates such a “pre-assignment” approach for the vertex cover problem as a typical combinatorial optimization problem and discusses its computational complexity. First, we show that the problem is ΣP2 -complete in general, while the problem becomes NP-complete when an input graph is bipartite. We then present an O(2.1996n)-time algorithm for general graphs and an O(1.9181n)-time algorithm for bipartite graphs, where n is the number of vertices. The latter is based on an FPT algorithm with O∗(3.6791τ) time for vertex cover number τ. Furthermore, we show that the problem for trees can be solved in O(1.4143n) time.

    DOI: 10.1609/aaai.v38i18.30060

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#HoriyamaK0SS24

  6. Faster Winner Determination Algorithms for (Colored) Arc Kayles

    Hanaka, T; Kiya, H; Lampis, M; Ono, H; Yoshiwatari, K

    SOFSEM 2024: THEORY AND PRACTICE OF COMPUTER SCIENCE   14519 巻   頁: 297 - 310   2024年

     詳細を見る

    出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Arc Kayles and Colored Arc Kayles, two-player games on a graph, are generalized versions of well-studied combinatorial games Cram and Domineering, respectively. In Arc Kayles, players alternately choose an edge to remove with its adjacent edges, and the player who cannot move is the loser. Colored Arc Kayles is similarly played on a graph with edges colored in black, white, or gray, while the black (resp., white) player can choose only a gray or black (resp., white) edge. For Arc Kayles, the vertex cover number (i.e., the minimum size of a vertex cover) is an essential invariant because it is known that twice the vertex cover number upper bounds the number of turns of Arc Kayles, and for the winner determination of (Colored) Arc Kayles, 2O(τ2)nO(1)-time algorithms are known, where τ is the vertex cover number and n is the number of vertices. In this paper, we first give a polynomial kernel for Colored Arc Kayles parameterized by τ, which leads to a faster 2O(τlogτ)nO(1)-time algorithm for Colored Arc Kayles. We then focus on Arc Kayles on trees, and propose a 2.2361τnO(1)-time algorithm. Furthermore, we show that the winner determination Arc Kayles on a tree can be solved in O(1.3831n) time, which improves the best-known running time O(1.4143n). Finally, we show that Colored Arc Kayles is NP-hard, the first hardness result in the family of the above games.

    DOI: 10.1007/978-3-031-52113-3_21

    Web of Science

    Scopus

  7. Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

    Hanaka Tesshu, Ono Hirotaka, Sugiyama Kosuke

    International Journal of Networking and Computing   14 巻 ( 1 ) 頁: 26 - 39   2024年

     詳細を見る

    記述言語:英語   出版者・発行元:IJNC Editorial Committee  

    For an undirected graph G = (V,E) and a k-non-negative integer vector p = (p1, . . . , pk), a mapping l : V → N∪{0} is called an L(p)-labeling of G if |l(u) − l(v)| ≥ pd for any two distinct vertices u, v ∈ V with distance d, and the maximum value of {l(v) | v ∈ V } is called the span of l. Originally, L(p)-labeling of G for p = (2, 1) is introduced in the context of frequency assignment in radio networks, where ‘close’ transmitters must receive different frequencies and ‘very close’ transmitters must receive frequencies that are at least two frequencies apart so that they can avoid interference. L(p)-Labeling is the problem of finding the minimum span λp among L(p)-labelings of G, which is NP-hard for every non-zero p. L(p)-Labeling is well studied for specific p’s; in particular, many (exact or approximation) algorithms for general graphs or restricted classes of graphs are proposed for p = (2, 1) or more generally p = (p, q). Unfortunately, most algorithms strongly depend on the values of p, and it is not apparent to extend algorithms for p to ones for another p′ in general. In this paper, we give a simple polynomial-time reduction of L(p)-Labeling on graphs with a small diameter to Metric (Path) TSP, which enables us to use numerous results on (Metric) TSP. On the practical side, we can utilize various high-performance heuristics for TSP, such as Concordo and LKH, to solve our problem. On the theoretical side, we can see that the problem for any p under this framework is 1.5-approximable, and it can be solved by the Held-Karp algorithm in O(2nn2) time, where n is the number of vertices, and so on.

    DOI: 10.15803/ijnc.14.1_26

    CiNii Research

  8. Structural Parameterizations of Vertex Integrity [Best Paper]

    Gima, T; Hanaka, T; Kobayashi, Y; Murai, R; Ono, H; Otachi, Y

    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024   14549 巻   頁: 406 - 420   2024年

     詳細を見る

    出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.

    DOI: 10.1007/978-981-97-0566-5_29

    Web of Science

    Scopus

  9. Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP.

    Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

    International Journal of Networking and Computing   14 巻 ( 1 ) 頁: 26 - 39   2024年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    その他リンク: https://dblp.uni-trier.de/db/journals/ijnc/ijnc14.html#HanakaOS24

  10. An 8-approximation algorithm for <i>L</i>(2,1)-labeling of unit disk graphs

    Ono, H; Yamanaka, H

    DISCRETE APPLIED MATHEMATICS   341 巻   頁: 93 - 101   2023年12月

     詳細を見る

    掲載種別:研究論文(学術雑誌)   出版者・発行元:Discrete Applied Mathematics  

    Given a graph G=(V,E), an L(2,1)-labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u,v), |ℓ(u)−ℓ(v)|≥2 if u and v are adjacent, and ℓ(u)≠ℓ(v) if u and v are at distance 2. The L(2,1)-labeling problem is to minimize the range of ℓ (i.e., maxu∈V(ℓ(u))−minu∈V(ℓ(u))+1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L(2,1)-labeling of unit disk graphs.

    DOI: 10.1016/j.dam.2023.07.012

    Web of Science

    Scopus

  11. Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

    Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

    IPDPS Workshops 2023   abs/2303.01290 巻   2023年5月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.48550/arXiv.2303.01290

  12. Sequentially Swapping Tokens: Further on Graph Classes

    Kiya, H; Okada, Y; Ono, H; Otachi, Y

    SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE   13878 巻   頁: 222 - 235   2023年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the sequence of token swappings along the walk obtains one of the given token placements from the other one. This problem was introduced as Sequential Token Swapping by Yamanaka et al. [JGAA 2019], who showed that the problem is intractable in general but polynomial-time solvable for trees, complete graphs, and cycles. In this paper, we present a polynomial-time algorithm for block-cactus graphs, which include all previously known cases. We also present general tools for showing the hardness of problem on restricted graph classes such as chordal graphs and chordal bipartite graphs. We also show that the problem is hard on grids and king’s graphs, which are the graphs corresponding to the 15 puzzle and its variant with relaxed moves.

    DOI: 10.1007/978-3-031-23101-8_15

    Web of Science

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/sofsem/sofsem2023.html#KiyaOOO23

  13. Shortest Beer Path Queries Based on Graph Decomposition

    Hanaka T., Ono H., Sadakane K., Sugiyama K.

    Leibniz International Proceedings in Informatics, LIPIcs   283 巻   頁: 37 - 20   2023年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Leibniz International Proceedings in Informatics, LIPIcs  

    Given a directed edge-weighted graph G = (V, E) with beer vertices B ⊆ V , a beer path between two vertices u and v is a path between u and v that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. We consider indexing problems on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size O(n) for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in O(α(n)) time, where α(·) is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size O(m + nr2) based on the triconnected component decomposition, where r is the size of the largest triconnected component. For a given query u, v ∈ V , our algorithm using the indexes can output the beer distance in query time O(α(m)). In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs.

    DOI: 10.4230/LIPIcs.ISAAC.2023.37

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/isaac/isaac2023.html#HanakaOSS23

  14. Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

    Hanaka, T; Ono, H; Sugiyama, K

    2023 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS, IPDPSW     頁: 308 - 313   2023年

     詳細を見る

    出版者・発行元:2023 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2023  

    For an undirected graph G=(V, E) and a k-nonnegative integer vector p=(p_1, L˙, p_k), a mapping l: V → N ∪0 is called an L(p)-labeling of G if |l(u)-l(v)| ≥ p_d for any two distinct vertices u, v in V with distance d, and the maximum value of l(v) mid v in V is called the span of l. Originally, L(p)-labeling of G for p=(2,1) is introduced in the context of frequency assignment in radio networks, where 'close' transmitters must receive different frequencies and 'very close' transmitters must receive frequencies that are at least two frequencies apart so that they can avoid interference. L(p) LABELING is the problem of finding the minimum span λp among L(p)-labelings of G, which is NP-hard for every non-zero p. L(p)-LABELING is well studied for specific p 's; in particular, many (exact or approximation) algorithms for general graphs or restricted classes of graphs are proposed for p=(2,1) or more generally p=(p, q). Unfortunately, most algorithms strongly depend on the values of p, and it is not apparent to extend algorithms for p to ones for another p' in general. In this paper, we give a simple polynomial-time reduction of L(p)-LABELING on graphs with a small diameter to METRIC (PATH) TSP, which enables us to use numerous results on (METRIC) TSP. On the practical side, we can utilize various high-performance heuristics for TSP, such as Concordo and LKH, to solve our problem. On the theoretical side, we can see that the problem for any p under this framework is 1.5 -approximable, and it can be solved by the Held-Karp algorithm in O2^n n^2) time, where n is the number of vertices, and so on.

    DOI: 10.1109/IPDPSW59300.2023.00059

    Web of Science

    Scopus

  15. 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   321 巻   頁: 281 - 294   2022年11月

     詳細を見る

    記述言語:日本語   出版者・発行元: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

  16. 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   223 巻   2022年6月

     詳細を見る

    記述言語:日本語   出版者・発行元: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

  17. 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   3 巻   頁: 1616 - 1617   2022年

     詳細を見る

    記述言語:日本語   出版者・発行元: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

  18. 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)   13584 LNCS 巻   頁: 421 - 435   2022年

     詳細を見る

    記述言語:日本語   出版者・発行元: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

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

    Hanaka T., Kawai K., Ono H.

    Journal of Graph Algorithms and Applications   26 巻 ( 2 ) 頁: 241 - 255   2022年

     詳細を見る

    記述言語:日本語   出版者・発行元: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

  20. Reallocation Problems with Minimum Completion Time

    Ishii, T; Kawahara, J; Makino, K; Ono, H

    COMPUTING AND COMBINATORICS, COCOON 2022   13595 巻   頁: 292 - 304   2022年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost (e.g., transition time), non-fungible, and reallocated among warehouses in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P = NP. We then consider to solve the problem by relaxing capacity constraints, which we call the capacity augmentation, and derive a reallocation schedule feasible with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large.

    DOI: 10.1007/978-3-031-22105-7_26

    Web of Science

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/cocoon/cocoon2022.html#IshiiKMO22

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

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

    情報・システムソサイエティ誌   26 巻 ( 2 ) 頁: 10 - 11   2021年8月

     詳細を見る

    記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

    DOI: 10.1587/ieiceissjournal.26.2_10

    CiNii Research

  22. Staging of astrocytopathy and complement activation in neuromyelitis optica spectrum disorders

    Takai Y., Misu T., Suzuki H., Takahashi T., Okada H., Tanaka S., Okita K., Sasou S., Watanabe M., Namatame C., Matsumoto Y., Ono H., Kaneko K., Nishiyama S., Kuroda H., Nakashima I., Lassmann H., Fujihara K., Itoyama Y., Aoki M.

    Brain   144 巻 ( 8 ) 頁: 2401 - 2415   2021年8月

     詳細を見る

    出版者・発行元:Brain  

    Aquaporin 4 (AQP4)-IgG-positive neuromyelitis optica spectrum disorder (AQP4-IgG+NMOSD) is an autoimmune astrocytopathic disease pathologically characterized by the massive destruction and regeneration of astrocytes with diverse types of tissue injury with or without complement deposition. However, it is unknown whether this diversity is derived from differences in pathological processes or temporal changes. Furthermore, unlike for the demyelinating lesions in multiple sclerosis, there has been no staging of astrocytopathy in AQP4-IgG+NMOSD based on astrocyte morphology. Therefore, we classified astrocytopathy of the disease by comparing the characteristic features, such as AQP4 loss, inflammatory cell infiltration, complement deposition and demyelination activity, with the clinical phase. We performed histopathological analyses in eight autopsied cases of AQP4-IgG+NMOSD. Cases comprised six females and two males, with a median age of 56.5 years (range, 46-71 years) and a median disease duration of 62.5 months (range, 0.6-252 months). Astrocytopathy in AQP4-IgG+NMOSD was classified into the following four stages defined by the astrocyte morphology and immunoreactivity for GFAP: (i) astrocyte lysis: extensive loss of astrocytes with fragmented and/or dust-like particles; (ii) progenitor recruitment: loss of astrocytes except small nucleated cells with GFAP-positive fibre-forming foot processes; (iii) protoplasmic gliosis: presence of star-shaped astrocytes with abundant GFAP-reactive cytoplasm; and (iv) fibrous gliosis: lesions composed of densely packed mature astrocytes. The astrocyte lysis and progenitor recruitment stages dominated in clinically acute cases (within 2 months after the last recurrence). Findings common to both stages were the loss of AQP4, a decreased number of oligodendrocytes, the selective loss of myelin-associated glycoprotein and active demyelination with phagocytic macrophages. The infiltration of polymorphonuclear cells and T cells (CD4-dominant) and the deposition of activated complement (C9neo), which reflects the membrane attack complex, a hallmark of acute NMOSD lesions, were selectively observed in the astrocyte lysis stage (98.4% in astrocyte lysis, 1.6% in progenitor recruitment, and 0% in protoplasmic gliosis and fibrous gliosis). Although most of the protoplasmic gliosis and fibrous gliosis lesions were accompanied by inactive demyelinated lesions with a low amount of inflammatory cell infiltration, the deposition of complement degradation product (C3d) was observed in all four stages, even in fibrous gliosis lesions, suggesting the past or chronic occurrence of complement activation, which is a useful finding to distinguish chronic lesions in NMOSD from those in multiple sclerosis. Our staging of astrocytopathy is expected to be useful for understanding the unique temporal pathology of AQP4-IgG+NMOSD.

    DOI: 10.1093/brain/awab102

    Scopus

  23. 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   2020-May 巻   頁: 1777 - 1779   2020年

     詳細を見る

    記述言語:日本語   出版者・発行元: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

  24. Hedonic Seat Arrangement Problems 査読有り 国際共著

    小野 廣隆

    Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems   - 巻   頁: 1777 - 1779   2020年

     詳細を見る

  25. Collecting Balls on a Line by Robots with Limited Energy

    Hanaka, T; Droguett, NH; Kurita, K; Ono, H; Otachi, Y

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E107.D 巻 ( 3 ) 頁: 325 - 327   2024年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 電子情報通信学会  

    In this paper, we study Ball Collecting with Limited Energy, which is a problem of scheduling robots with limited energy confined to a line to catch moving balls that eventually cross the line. For this problem, we show the NP-completeness of the general case and some algorithmic results for some cases with a small number of robots.

    DOI: 10.1587/transinf.2023fcl0003

    Web of Science

    Scopus

    CiNii Research

  26. On a Spectral Lower Bound of Treewidth

    Gima, T; Hanaka, T; Noro, K; Ono, H; Otachi, Y

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E107.D 巻 ( 3 ) 頁: 328 - 330   2024年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 電子情報通信学会  

    In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

    DOI: 10.1587/transinf.2023fcl0002

    Web of Science

    Scopus

    CiNii Research

  27. On the Computational Complexity of Generalized Common Shape Puzzles

    Banbara, M; Minato, S; Ono, H; Uehara, R

    SOFSEM 2024: THEORY AND PRACTICE OF COMPUTER SCIENCE   14519 巻   頁: 55 - 68   2024年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S1 and S2 of polyominoes. The first puzzle asks us to form the same shape using polyominoes in S1 and S2. We demonstrate that this is polynomial-time solvable if S1 and S2 have constant numbers of polyominoes, and it is strongly NP-complete in general. The second puzzle allows us to make copies of the pieces in S1 and S2. That is, a polyomino in S1 can be used multiple times to form a shape. This is a generalized version of the classical puzzle known as the common multiple shape puzzle. For two polyominoes P and Q, the common multiple shape is a shape that can be formed by many copies of P and many copies of Q. We show that the second puzzle is undecidable in general. The undecidability is demonstrated by a reduction from a new type of undecidable puzzle based on tiling. Nevertheless, certain concrete instances of the common multiple shape can be solved in a practical time. We present a method for determining the common multiple shape for provided tuples of polyominoes and outline concrete results, which improve on the previously known results in the puzzle community.

    DOI: 10.1007/978-3-031-52113-3_4

    Web of Science

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/sofsem/sofsem2024.html#BanbaraMOU24

  28. Shortest Longest-Path Graph Orientations

    Asahiro Y., Jansson J., Melkman A.A., Miyano E., Ono H., Xue Q., Zakov S.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   14422 LNCS 巻   頁: 141 - 154   2024年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph G= (V, E) in which every edge { u, v} ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions (u, v) and (v, u), and asks for an orientation, i.e., an assignment of a direction to each edge of G, such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

    DOI: 10.1007/978-3-031-49190-0_10

    Scopus

  29. An improved spectral lower bound of treewidth.

    Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi

    CoRR   abs/2404.08520 巻   2024年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2404.08520

  30. Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints

    Kobayashi, Y; Kurita, K; Matsui, Y; Ono, H

    COMBINATORIAL ALGORITHMS, IWOCA 2024   14764 巻   頁: 232 - 246   2024年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.1007/978-3-031-63021-7_18

    Web of Science

    その他リンク: https://dblp.uni-trier.de/db/conf/iwoca/iwoca2024.html#KobayashiKMO24

  31. Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs

    Hanaka T., Ikeyama A., Ono H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   14461 LNCS 巻   頁: 392 - 405   2023年12月

     詳細を見る

    担当区分:責任著者   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Fractional hedonic games are coalition formation games where the utility of a player is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition formation games that can be succinctly represented. Due to their applicability in network clustering and their relationship to graph hedonic games, fractional hedonic games have been extensively studied from various perspectives. However, finding welfare-maximizing partitions in fractional hedonic games is a challenging task due to the nonlinearity of utilities. In fact, it has been proven to be NP-hard in general and can be solved in polynomial time only for a limited number of graph classes, such as trees. This paper presents (pseudo)polynomial-time algorithms to compute welfare-maximizing partitions in fractional hedonic games on tree-like graphs. We consider two types of social welfare measures: utilitarian and egalitarian. Tree-like graphs refer to graphs with bounded treewidth and block graphs. An NP-hardness result demonstrates that the pseudopolynomial-time solvability is the best possible under the assumption P ≠ NP.

    DOI: 10.1007/978-3-031-49611-0_28

    Scopus

  32. Reconfiguration of cliques in a graph

    Ito, T; Ono, H; Otachi, Y

    DISCRETE APPLIED MATHEMATICS   333 巻   頁: 43 - 58   2023年7月

     詳細を見る

    掲載種別:研究論文(学術雑誌)   出版者・発行元:Discrete Applied Mathematics  

    We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques from the viewpoint of polynomial-time solvability. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. Furthermore, we show that the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

    DOI: 10.1016/j.dam.2023.01.026

    Web of Science

    Scopus

  33. Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

    Hanaka T., Ono H., Otachi Y., Uda S.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13898 巻   頁: 263 - 277   2023年4月

     詳細を見る

    掲載種別:論文集(書籍)内論文   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    A dominating set S of graph G is called an r-grouped domR such that the size of each unit is r and the subgraph of G induced by is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets , paired dominating sets), and connected dominating sets (r is arbitrary and . In this paper, we investigate the computational complexity of r -Grouped Dominating Set, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r -Grouped Dominating Set is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r -Grouped Dominating Set for every fixed is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r -Grouped Dominating Set is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic This fixed-parameter tractability is good news, but the running time is not practical. We then design an -time algorithm for general where is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., we can speed up the algorithm, whose running time becomes We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r -Grouped Dominating Set.

    DOI: 10.1007/978-3-031-30448-4_19

    Scopus

  34. On the Computational Complexity of Generalized Common Shape Puzzles.

    Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono, Ryuhei Uehara

    CoRR   abs/2305.10749 巻   2023年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2305.10749

  35. Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.

    Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono

    CoRR   abs/2308.16426 巻   2023年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2308.16426

  36. Approximation Algorithms for the Longest Run Subsequence Problem

    Asahiro Y., Gong M., Lin G., Ono H., Eto H., Jansson J., Miyano E., Tanaka S.

    Leibniz International Proceedings in Informatics, LIPIcs   259 巻   頁: 2 - 12   2023年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Leibniz International Proceedings in Informatics, LIPIcs  

    We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s1 · · · sn over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S′ of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S∗ of S such that the length |S∗| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time k+1/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 2/3 to 4/3.

    DOI: 10.4230/LIPIcs.CPM.2023.2

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/cpm/cpm2023.html#AsahiroEG0LMOT23

  37. Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover.

    Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki

    CoRR   abs/2312.10599 巻   2023年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2312.10599

  38. Shortest Beer Path Queries based on Graph Decomposition.

    Tesshu Hanaka, Hirotaka Ono 0001, Kunihiko Sadakane, Kosuke Sugiyama

    CoRR   abs/2307.02787 巻   2023年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2307.02787

  39. Turning Tiles is PSPACE-complete.

    Kanae Yoshiwatari, Hironori Kiya, Koki Suetsugu, Tesshu Hanaka, Hirotaka Ono 0001

    CoRR   abs/2310.01983 巻   2023年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2310.01983

  40. Parameterized Complexity of (<i>A</i>, <i>l</i>)-Path Packing 査読有り

    Belmonte, R; Hanaka, T; Kanzaki, M; Kiyomi, M; Kobayashi, Y; Kobayashi, Y; Lampis, M; Ono, H; Otachi, Y

    ALGORITHMICA   84 巻 ( 4 ) 頁: 871 - 895   2022年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(研究会,シンポジウム資料等)   出版者・発行元:Algorithmica  

    Given a graph G= (V, E) , A⊆ V, and integers k and ℓ, the (A, ℓ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly ℓ that have endpoints in A and internal points in V\ A. We study the parameterized complexity of this problem with parameters |A|, ℓ, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ≤ 3 , while it is NP-complete for constant ℓ≥ 4. We also show that the problem is W[1]-hard parameterized by pathwidth+ | A| , while it is fixed-parameter tractable parameterized by treewidth+ ℓ. Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at mostℓ. We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or ℓ is a constant.

    DOI: 10.1007/s00453-021-00875-y

    Web of Science

    Scopus

  41. Upper and lower degree-constrained graph orientation with minimum penalty 査読有り

    Asahiro, Y; Jansson, J; Miyano, E; Ono, H

    THEORETICAL COMPUTER SCIENCE   900 巻   頁: 53 - 78   2022年1月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Theoretical Computer Science  

    In the degree-constrained graph orientation problem, the input is an unweighted, undirected graph G=(V,E) and nonnegative integers av and bv (with av≤bv) for each v∈V, and the objective is to assign a direction to every edge in E in such a way that for each v∈V, the number of outgoing edges in the resulting directed graph lies in the interval [av,bv]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty ∑v∈Vcv, where cv is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O(|E|1.5min⁡{log⁡(|E|⋅C),|E|0.5log⁡Δlog⁡|E|}) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ, the problem with any penalty function can be solved exactly in O(|V|log⁡Δ) time and O(τ2Δ2τ+2|V|) time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights.

    DOI: 10.1016/j.tcs.2021.11.019

    Web of Science

    Scopus

  42. 構造的オラクルによる不完全情報TANHINMINのモデリング 査読有り

    KIYA Hironori, OHTO Katsuki, ONO Hirotaka

    情報処理学会論文誌トランザクション 数理モデル化と応用(Web)   15 巻 ( 1 ) 頁: 10 - 17   2022年1月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)  

    J-GLOBAL

  43. Winner Determination Algorithms for Graph Games with Matching Structures

    Yoshiwatari K., Kiya H., Hanaka T., Ono H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13270 LNCS 巻   頁: 509 - 522   2022年

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in O∗(2n) time by a simple algorithm, where n is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O∗(1.4143τ2+3.17τ), O∗(1.3161τ2+4τ), and O∗(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O∗((n/ ν+ 1 )ν) -time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O∗(2n2) (= O(1. 4143n) ) time, which improves O∗(3n3) (= O(1. 4423n) ) by a direct adjustment of the analysis of Bodlaender et al.’s O∗(3n3) -time algorithm for Node Kayles.

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

    Scopus

    その他リンク: https://dblp.uni-trier.de/db/conf/iwoca/iwoca2022.html#YoshiwatariKHO22

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

    Tesshu Hanaka, Toshiyuki Hirose, Hirotaka Ono

    21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS)     頁: 1616 - 1617   2022年

     詳細を見る

    掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

    その他リンク: https://dl.acm.org/doi/10.5555/3535850.3536053

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

    Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

    CoRR   abs/2211.05307 巻   2022年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    DOI: 10.48550/arXiv.2211.05307

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

    木谷 裕紀, 小野 廣隆

    システム/制御/情報   65 巻 ( 10 ) 頁: 415 - 420   2021年10月

     詳細を見る

    記述言語:日本語   出版者・発行元:一般社団法人 システム制御情報学会  

    DOI: 10.11509/isciesci.65.10_415

    CiNii Research

  47. Computing the Winner of 2-Player TANHINMIN

    Kiya Hironori, Ohto Katsuki, Ono Hirotaka

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E104.A 巻 ( 9 ) 頁: 1134 - 1141   2021年9月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 電子情報通信学会  

    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 n. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.

    DOI: 10.1587/transfun.2020dmp0026

    Web of Science

    Scopus

  48. Computing L(p, 1)-Labeling with Combined Parameters 査読有り

    Hanaka T., Kawai K., Ono H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12635 LNCS 巻   頁: 208 - 220   2021年2月

     詳細を見る

    記述言語:日本語   掲載種別:論文集(書籍)内論文   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    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, 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.1007/978-3-030-68211-8_17

    Scopus

  49. Graph Orientation with Edge Modifications 査読有り 国際共著

    Asahiro, Y; Jansson, J; Miyano, E; Ono, H; Sandhya, TP

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   32 巻 ( 02 ) 頁: 209 - 233   2021年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:International Journal of Foundations of Computer Science  

    The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H 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) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-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

  50. Fairness norm through social networks: a simulation approach

    Rifki O., Ono H.

    Computational Social Networks   8 巻 ( 1 )   2021年

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

  51. Reallocation Problems with Minimum Completion Time.

    Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

    CoRR   abs/2111.02579 巻   2021年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    その他リンク: https://dblp.uni-trier.de/db/journals/corr/corr2111.html#abs-2111-02579

  52. Graph orientation with splits 査読有り 国際共著

    Asahiro, Y; Jansson, J; Miyano, E; Nikpey, H; Ono, H

    THEORETICAL COMPUTER SCIENCE   844 巻   頁: 16 - 25   2020年12月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Theoretical Computer Science  

    The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

    DOI: 10.1016/j.tcs.2020.07.013

    Web of Science

    Scopus

  53. Exact algorithms for the repetition-bounded longest common subsequence problem 査読有り 国際共著

    Asahiro, Y; Jansson, J; Lin, GH; Miyano, E; Ono, H; Utashima, T

    THEORETICAL COMPUTER SCIENCE   838 巻   頁: 238 - 249   2020年10月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Theoretical Computer Science  

    In this paper, we study exact, exponential-time algorithms for a variant of the classic LONGEST COMMON SUBSEQUENCE problem called the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint Cocc be a function Cocc:S→N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint Cocc, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s∈S appears at most Cocc(s) times in the obtained subsequence. The special case where Cocc(s)=1 for every symbol s∈S is known as the REPETITION-FREE LONGEST COMMON SUBSEQUENCE problem (RFLCS) and has been studied previously; e.g., in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that |X|≤|Y| and |X|=n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O(1.44225n). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O(1.44225n) for any occurrence constraint Cocc, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O(1.41422n) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

    DOI: 10.1016/j.tcs.2020.07.042

    Web of Science

    Scopus

  54. Parameterized complexity of independent set reconfiguration problems 査読有り 国際共著

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

    DISCRETE APPLIED MATHEMATICS   283 巻   頁: 336 - 345   2020年9月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Discrete Applied Mathematics  

    Suppose that we are given two independent sets I0 and Ir of a graph such that |I0|=|Ir|, and imagine that a token is placed on each vertex in I0. Then, the TOKEN JUMPING problem is to determine whether there exists a sequence of independent sets which transforms I0 into Ir so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I0 and Ir with the minimum number of token movements. We finally show that one of the results for TOKEN JUMPING can be extended to a more generalized reconfiguration problem for independent sets, called TOKEN ADDITION AND REMOVAL.

    DOI: 10.1016/j.dam.2020.01.022

    Web of Science

    Scopus

  55. Independent Set Reconfiguration Parameterized by Modular-Width 査読有り

    Belmonte, R; Hanaka, T; Lampis, M; Ono, H; Otachi, Y

    ALGORITHMICA   82 巻 ( 9 ) 頁: 2586 - 2605   2020年9月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Algorithmica  

    Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules TAR, TJ, and TS. The result under TAR resolves an open problem posed by Bonsma (J Graph Theory 83(2):164–195, 2016).

    DOI: 10.1007/s00453-020-00700-y

    Web of Science

    Scopus

    その他リンク: http://link.springer.com/article/10.1007/s00453-020-00700-y/fulltext.html

  56. Parameterized Complexity of (A,l)-Path Packing 査読有り 国際共著

    Belmonte R., Hanaka T., Kanzaki M., Kiyomi M., Kobayashi Y., Kobayashi Y., Lampis M., Ono H., Otachi Y.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12126 LNCS 巻   頁: 43 - 55   2020年6月

     詳細を見る

    記述言語:日本語   掲載種別:論文集(書籍)内論文   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Given a graph G = (V, E), (Formula Presented), and integers k and ℓ, the (A, ℓ)-Path Packing problem asks to find k vertex-disjoint paths of length ℓ that have endpoints in A and internal points in V \ A. We study the parameterized complexity of this problem with parameters |A|, ℓ, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ ≤ 3, while it is NP-complete for constant ℓ ≥ 4. We also show that the problem is W[1]-hard parameterized by pathwidth+|A|, while it is fixed-parameter tractable parameterized by treewidth + ℓ.

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

    Scopus

  57. Parameterized complexity of safe set 査読有り 国際共著

    Belmonte R., Hanaka T., Katsikarelis I., Lampis M., Ono H., Otachi Y.

    Journal of Graph Algorithms and Applications   24 巻 ( 3 ) 頁: 215 - 245   2020年4月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Journal of Graph Algorithms and Applications  

    In this paper we study the problem of finding a small safe set S in a graph G, i.e., a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in G − S. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth pw and cannot be solved in time no(pw) unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number vc unless PH = Σp but (3) it is fixed-parameter tractable (FPT) when parameterized by3,the neighborhood diversity nd, and (4) it can be solved in time nf(cw) for some double exponential function f where cw is the clique-width. We also present (5) a faster fixed-parameter algorithm when parameterized by the solution size.

    DOI: 10.7155/jgaa.00528

    Scopus

  58. Space-Efficient Algorithms for Longest Increasing Subsequence 査読有り 国際共著

    Kiyomi, M; Ono, H; Otachi, Y; Schweitzer, P; Tarui, J

    THEORY OF COMPUTING SYSTEMS   64 巻 ( 3 ) 頁: 522 - 541   2020年4月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Theory of Computing Systems  

    Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(nlog n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n≤s≤n, we present algorithms that use O(slog n) bits and O(1s⋅n2⋅logn) time for computing the length of a longest increasing subsequence, and O(1s⋅n2⋅log2n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

    DOI: 10.1007/s00224-018-09908-6

    Web of Science

    Scopus

    その他リンク: http://link.springer.com/article/10.1007/s00224-018-09908-6/fulltext.html

  59. Hedonic Seat Arrangement Problems. 査読有り 国際誌

    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     頁: 1777 - 1779   2020年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:International Foundation for Autonomous Agents and Multiagent Systems  

    その他リンク: https://dblp.uni-trier.de/conf/atal/2020

  60. Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium 査読有り

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

    SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE   12011 巻   頁: 627 - 635   2020年

     詳細を見る

    記述言語:日本語   掲載種別:論文集(書籍)内論文   出版者・発行元:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). In the model, a player chooses an initial vertex of the graph, from which information by the player spreads through the edges connected with the initial vertex. If a vertex that is not yet influenced by any information receives information by a player, it is influenced by the information and it diffuses it to adjacent vertices. A vertex that simultaneously receives two or more types of information does not diffuse any type of information from then on. The objective of a player is to maximize the number of vertices influenced by the player’s information. 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 block graphs, split graphs and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that there is an instance with no pure Nash equilibrium on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

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

    Web of Science

    Scopus

  61. The computational complexity of the gear placement problem

    Hama, VMF; Kanazawa, S; Hu, Y; Imahori, S; Ono, H; Yagiura, M

    JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING   14 巻 ( 5 ) 頁: JAMDSM0069 - JAMDSM0069   2020年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 日本機械学会  

    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.

    DOI: 10.1299/jamdsm.2020jamdsm0069

    Web of Science

    Scopus

    CiNii Research

  62. Fair Ride Allocation on a Line.

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

    CoRR   abs/2007.08045 巻   2020年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    その他リンク: https://dblp.uni-trier.de/db/journals/corr/corr2007.html#abs-2007-08045

  63. A faster parameterized algorithm for PSEUDOFOREST DELETION 査読有り

    Bodlaender Hans L., Ono Hirotaka, Otachi Yota

    DISCRETE APPLIED MATHEMATICS   236 巻   頁: 42-56   2018年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2017.10.018

    Web of Science

  64. Finding environmentally critical transmission sectors, transactions, and paths in global supply chain networks 査読有り

    Hanaka Tesshu, Kagawa Shigemi, Ono Hirotaka, Kanemoto Keiichiro

    ENERGY ECONOMICS   68 巻   頁: 44-52   2017年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.eneco.2017.09.012

    Web of Science

  65. 圧縮アルゴリズムに基づく超大規模データからの組合せ構造抽出

    小野 廣隆

    旭硝子財団助成研究成果報告 Reports of research assisted by the Asahi Glass Foundation     頁: 1-8   2017年

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  66. Subexponential fixed-parameter algorithms for partial vector domination 査読有り

    Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    DISCRETE OPTIMIZATION   22 巻   頁: 111-121   2016年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.disopt.2016.01.003

    Web of Science

  67. The complexity of dominating set reconfiguration 査読有り

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

    THEORETICAL COMPUTER SCIENCE   651 巻   頁: 37-49   2016年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2016.08.016

    Web of Science

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

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

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   116 巻 ( 116 ) 頁: 81-87   2016年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    小野 廣隆

    オペレーションズ・リサーチ   61 巻 ( 2 ) 頁: 109-111   2016年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  70. Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation 査読有り

    Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

    THEORY OF COMPUTING SYSTEMS   58 巻 ( 1 ) 頁: 60-93   2016年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00224-014-9565-5

    Web of Science

  71. Linear-time algorithm for sliding tokens on trees 査読有り

    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   600 巻   頁: 132-142   2015年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2015.07.037

    Web of Science

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

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

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2015 巻   頁: 252-253   2015年9月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

    土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2015 巻   頁: 130-131   2015年9月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  74. Approximability of minimum certificate dispersal with tree structures 査読有り

    Izumi Taisuke, Izumi Tomoko, Ono Hirotaka, Wada Koichi

    THEORETICAL COMPUTER SCIENCE   591 巻   頁: 5-14   2015年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2015.01.007

    Web of Science

  75. The searchlight problem for road networks 査読有り

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

    THEORETICAL COMPUTER SCIENCE   591 巻   頁: 28-59   2015年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2015.04.026

    Web of Science

  76. On the approximability and hardness of minimum topic connected overlay and its special instances (vol 429, pg 144, 2012) 査読有り

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

    THEORETICAL COMPUTER SCIENCE   562 巻   頁: 660-661   2015年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2014.11.001

    Web of Science

  77. PATTERN FORMATION BY OBLIVIOUS ASYNCHRONOUS MOBILE ROBOTS 査読有り

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

    SIAM JOURNAL ON COMPUTING   44 巻 ( 3 ) 頁: 740-785   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1137/140958682

    Web of Science

  78. Finding All Longest Common Segments in Protein Structures Efficiently 査読有り

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

    IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS   12 巻 ( 3 ) 頁: 644-655   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1109/TCBB.2014.2372782

    Web of Science

  79. Subgraph Domatic Problem and Writing Capacity of Memory Devices with Restricted State Transitions 査読有り

    Wadayama Tadashi, Izumi Taisuke, Ono Hirotaka

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  80. Reconfiguration of Cliques in a Graph 査読有り

    Ito Takehiro, Ono Hirotaka, Otachi Yota

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015)   9076 巻   頁: 212-223   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    Web of Science

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

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

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   114 巻 ( 312 ) 頁: 105-112   2014年11月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

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

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   114 巻 ( 313 ) 頁: 105-112   2014年11月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

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

    研究報告アルゴリズム(AL)   2014 巻 ( 19 ) 頁: 1-8   2014年11月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

  84. Base-object location problems for base-monotone regions 査読有り

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

    THEORETICAL COMPUTER SCIENCE   555 巻   頁: 71-84   2014年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2013.11.030

    Web of Science

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

    土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2014 巻   頁: 198-199   2014年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2014 巻   頁: 158-159   2014年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  87. Reconfiguration of list L(2,1)-labelings in a graph 査読有り

    Ito Takehiro, Kawamura Kazuto, Ono Hirotaka, Zhou Xiao

    THEORETICAL COMPUTER SCIENCE   544 巻   頁: 84-97   2014年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2014.04.011

    Web of Science

  88. Approximating the path-distance-width for AT-free graphs and graphs in related classes 査読有り

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

    DISCRETE APPLIED MATHEMATICS   168 巻   頁: 69-77   2014年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2012.11.015

    Web of Science

  89. Robustness Analysis of Evolutionary Algorithms to Portfolio Optimization Against Errors in Asset Means 査読有り

    Rifki Omar, Ono Hirotaka

    OPERATIONS RESEARCH PROCEEDINGS 2013     頁: 369-375   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    Web of Science

  90. Depth-First Search Using O(n) Bits 査読有り

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

    ALGORITHMS AND COMPUTATION, ISAAC 2014   8889 巻   頁: 553-564   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    Web of Science

  91. (Total) Vector Domination for Graphs with Bounded Branchwidth 査読有り

    Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    LATIN 2014: THEORETICAL INFORMATICS   8392 巻   頁: 238-249   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  92. Fixed-Parameter Tractability of Token Jumping on Planar Graphs 査読有り

    Ito Takehiro, Kaminski Marcin, Ono Hirotaka

    ALGORITHMS AND COMPUTATION, ISAAC 2014   8889 巻   頁: 208-219   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    Web of Science

  93. Polynomial-Time Algorithm for Sliding Tokens on Trees 査読有り

    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   8889 巻   頁: 389-400   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    Web of Science

  94. Approximability of Latin Square Completion-Type Puzzles 査読有り

    Haraguchi Kazuya, Ono Hirotaka

    FUN WITH ALGORITHMS   8496 巻   頁: 218-229   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  95. On the Parameterized Complexity for Token Jumping on Graphs 査読有り

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

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)   8402 巻   頁: 341-351   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  96. 次数制約のあるグラフ有向化問題の近似について (Theoretical Foundations of Computing)

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

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   113 巻 ( 371 ) 頁: 123-130   2013年12月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

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

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   113 巻 ( 371 ) 頁: 7-14   2013年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    グラフ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へ遷移させる最短の系列を多項式時間で見つけることができる.

  98. Optimal approximability of bookmark assignments 査読有り

    Asahiro Yuichi, Miyano Eiji, Murata Toshihide, Ono Hirotaka

    DISCRETE APPLIED MATHEMATICS   161 巻 ( 16-17 ) 頁: 2361-2366   2013年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2013.05.018

    Web of Science

  99. A Linear Time Algorithm for L(2,1)-Labeling of Trees 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHMICA   66 巻 ( 3 ) 頁: 654-681   2013年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-012-9657-z

    Web of Science

  100. BLOCKSUM is NP-Complete 査読有り

    Haraguchi Kazuya, Ono Hirotaka

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E96D 巻 ( 3 ) 頁: 481-488   2013年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1587/transinf.E96.D.481

    Web of Science

  101. Route-Enabling Graph Orientation Problems 査読有り

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

    ALGORITHMICA   65 巻 ( 2 ) 頁: 317-338   2013年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-011-9589-z

    Web of Science

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

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

    IBEC   33 巻 ( 5 ) 頁: 40-43   2013年1月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  103. ポートフォリオ最適化のための進化アルゴリズム感応度測定。

    Rifki Omar, 小野 廣隆

    電気関係学会九州支部連合大会講演論文集   2013 巻 ( 0 ) 頁: 181-182   2013年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    Mean-Variance Portfolio optimization is highly sensitive to errors in assets means, when solved by Quadratic Programming (QP). We propose a simulation-based evaluation method for the sensitivity, applied to QP and the Evolutionary Algorithms (EA): Genetic Algorithm, Evolution Strategy, Particle Swarm Optimization and Differential Evolution. Comparisons between variants of EAs and QP are made based on assessing the performance, under multiple perturbed runs, of several 'optimal' portfolios. Computational experiments show that many individuals of EAs population outperform QP optimal solution.

  104. COALESCING RANDOM WALKS AND VOTING ON CONNECTED GRAPHS 査読有り

    Cooper Colin, Elsaesser Robert, Ono Hirotaka, Radzik Tomasz

    SIAM JOURNAL ON DISCRETE MATHEMATICS   27 巻 ( 4 ) 頁: 1748-1758   2013年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1137/120900368

    Web of Science

  105. On space complexity of self-stabilizing leader election in mediated population protocol 査読有り

    Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

    DISTRIBUTED COMPUTING   25 巻 ( 6 ) 頁: 451-460   2012年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00446-012-0173-9

    Web of Science

  106. RA-002 文字列圧縮を用いたネットワークセキュリティにおけるインシデント検出(アルゴリズムと応用(2),A分野:モデル・アルゴリズム・プログラミング)

    衛藤 公希, 小野 廣隆, 山下 雅史, 竹内 純一

    情報科学技術フォーラム講演論文集   11 巻 ( 1 ) 頁: 9-16   2012年9月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  107. Deductive Inference for the Interiors and Exteriors of Horn Theories 査読有り

    Makino Kazuhisa, Ono Hirotaka

    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC   13 巻 ( 3 )   2012年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1145/2287718.2287723

    Web of Science

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

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

    数理解析研究所講究録   1799 巻   頁: 130-136   2012年6月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1799 巻   頁: 123-129   2012年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

  110. The (p, q)-total labeling problem for trees 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    DISCRETE MATHEMATICS   312 巻 ( 8 ) 頁: 1407-1420   2012年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.disc.2012.01.007

    Web of Science

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

  112. On the approximability and hardness of minimum topic connected overlay and its special instances 査読有り

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2011.12.033

    Web of Science

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

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

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1109/IPDPSW.2012.107

    Web of Science

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s10878-009-9276-z

    Web of Science

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

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

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

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

    Discrete Applied Mathematics   159 巻 ( 7 ) 頁: 498-508   2011年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

    Asahiro Yuichi, Miyano Eiji, Ono Hirotaka

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2010.11.003

    Web of Science

  126. GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE 査読有り

    Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   22 巻 ( 3 ) 頁: 583-601   2011年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1142/S0129054111008246

    Web of Science

  127. DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)

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

    電子情報通信学会総合大会講演論文集   2011 巻 ( 1 ) 頁: "S-11"-"S-12"   2011年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  128. Broadcastings and digit tilings on three-dimensional torus networks 査読有り

    Okazaki Ryotaro, Ono Hirotaka, Sadahiro Taizo, Yamashita Masafumi

    THEORETICAL COMPUTER SCIENCE   412 巻 ( 4-5 ) 頁: 307-319   2011年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2010.09.028

    Web of Science

  129. グラフトポロジーを利用した高速ランダムウォークの設計

    小野 廣隆

    旭硝子財団助成研究成果報告     頁: 1-5   2011年

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  130. The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Delta+2 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    COMBINATORIAL ALGORITHMS   6460 巻   頁: 103-+   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  131. On the Approximability of Minimum Topic Connected Overlay and Its Special Instances 査読有り

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

    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011   6907 巻   頁: 376-387   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  132. Approximability of the Path-Distance-Width for AT-free Graphs 査読有り

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

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   6986 巻   頁: 271-+   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  133. 最大支配問題

    宮野 英次, 小野 廣隆

    電子情報通信学会技術研究報告. COMP, コンピュテーション   110 巻 ( 325 ) 頁: 53-60   2010年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    グラフにおける頂点/辺支配集合問題の新しい亜種について考える.ある頂点はその頂点自身と隣接点を支配すると言い,同様にある辺はその辺自身と隣接する辺を支配すると言う.グラフ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の多項式時間アルゴリズムが存在することを示す.

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

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

    研究報告アルゴリズム(AL)   2010 巻 ( 4 ) 頁: 1-5   2010年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    本論文は,自己安定リーダー選挙メディエイテッドポピュレーションプロトコル (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.

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

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

    研究報告アルゴリズム(AL)   2010 巻 ( 2 ) 頁: 1-8   2010年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    グラフ 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.

  136. A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)

    山田 陽介, 小野 廣隆, 来嶋 秀治, 山下 雅史

    情報科学技術フォーラム講演論文集   9 巻 ( 1 ) 頁: 231-232   2010年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  137. A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)

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

    情報科学技術フォーラム講演論文集   9 巻 ( 1 ) 頁: 205-206   2010年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  138. A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)

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

    情報科学技術フォーラム講演論文集   9 巻 ( 1 ) 頁: 207-208   2010年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  139. 高速復元可能な接尾辞配列圧縮法

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

    電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition)   93 巻 ( 8 ) 頁: 1567-1575   2010年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    大規模文字列データに対する高速な文字列検索は接尾辞配列(SA)を用いて実現できるが,SAには多くの容量が必要になってしまう.SAを圧縮する様々な方法が提案されているが,本論文では出現頻度の高いフレーズの検索が既存の圧縮法に比べて高速な圧縮法を提案する.提案手法では,SAをブロックに分割し,そのブロック内でソートを行い,差分をとったものを保存し,検索時は差分からソート後のSAを取り戻し,区間内をすべて逐次的に検索する.これで検索フレーズのすべての出現位置を得ることができる.実験により,特に検索フレーズの頻度が高い場合,多くの入力データで提案手法の性能が既存の方法より優れていることを示す.

  140. Local move connectedness of domino tilings with diagonal impurities 査読有り

    Nakano Fuminiko, Ono Hirotaka, Sadahiro Taizo

    DISCRETE MATHEMATICS   310 巻 ( 13-14 ) 頁: 1918-1931   2010年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.disc.2010.02.015

    Web of Science

  141. Approximability and inapproximability of the minimum certificate dispersal problem 査読有り

    Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

    THEORETICAL COMPUTER SCIENCE   411 巻 ( 31-33 ) 頁: 2773-2783   2010年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2010.03.029

    Web of Science

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

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

    数理解析研究所講究録   1691 巻   頁: 155-161   2010年6月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1691 巻   頁: 85-90   2010年6月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1691 巻   頁: 91-95   2010年6月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1691 巻   頁: 148-154   2010年6月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  146. THE SPACE COMPLEXITY OF LEADER ELECTION IN ANONYMOUS NETWORKS 査読有り

    Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   21 巻 ( 3 ) 頁: 427-440   2010年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1142/S0129054110007349

    Web of Science

  147. The hitting and cover times of Metropolis walks

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

    Theoretical Computer Science   411 巻 ( 16 ) 頁: 1889-1894   2010年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

  148. The hitting and cover times of Metropolis walks 査読有り

    Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    THEORETICAL COMPUTER SCIENCE   411 巻 ( 16-18 ) 頁: 1889-1894   2010年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2010.01.032

    Web of Science

  149. 全二分木の簡潔な表現

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

    研究報告アルゴリズム(AL)   2010 巻 ( 1 ) 頁: 1-8   2010年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた.本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる.提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり,右の子へ巡回するといった操作を定数時間で行うことができる.また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す.To take large-scale data efficiently, succinct data structures that support highspeed operations on compressed data have been developed. In this paper, we focus on full binary trees which are used as patricia tries. We propose for a succinct data structure whose size is n+o(n) bits. This representation enables constant time operations such as traversing from a internal node to its right child node. Then, we show that a suffix tree (ST) is compressible by converting it to a full binary tree.

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

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

    研究報告アルゴリズム(AL)   2010 巻 ( 1 ) 頁: 1-6   2010年1月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    大規模データに対する高速な文字列検索は接尾辞配列 (SA) を用いて実現できるが,SA には多くの容量が必要になってしまう.SA を圧縮する様々な方法が提案されているが,提案手法は,SA と転置インデックスを組み合わせることで,出現頻度の高いフレーズの検索が既存の索引に比べ高速な索引を実現する.最終的には実験により,以前提案した別手法5) と似た性能で,ある程度検索時間を調整可能であることを示す.String pattern matching for large-scale data is efficiently achieved by suffix array (SA), but SA requires a large space. Therefore, various methods to compress SA have been proposed. In this paper, we combine SA and Inverted index. As a result, performance of the proposed method is better than existing ones when searching frequent phrases. Experiments show that the proposed method is similar to one which is proposed by us in other times, and able to control search time at some level.

  151. The (p, q)-total Labeling Problem for Trees 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHMS AND COMPUTATION, PT 2   6507 巻   頁: 49-+   2010年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  152. Upper and Lower Bounds of Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol 査読有り

    Mizoguchi Ryu, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

    PRINCIPLES OF DISTRIBUTED SYSTEMS   6490 巻   頁: 491-503   2010年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  153. Pattern Formation through Optimum Matching by Oblivious CORDA Robots 査読有り

    Fujinaga Nao, Ono Hirotaka, Kijima Shuji, Yamashita Masafumi

    PRINCIPLES OF DISTRIBUTED SYSTEMS   6490 巻   頁: 1-15   2010年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

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

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

    研究報告アルゴリズム(AL)   2009 巻 ( 7 ) 頁: 1-8   2009年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    グラフの k-L(2, 1) -ラベリングとは,頂点への 0 から k までの整数値の割り当てであり,隣接頂点間では少なくとも 2,距離 2 の頂点間では少なくとも 1 の差があるもののことを言う.L(2, 1) -ラベリング問題とは,グラフに対する k-L(2, 1) ラベリングの中で最小の k を求めるものである.この問題は,木幅が 2 のグラフに対してでも NP 困難であることが知られている.一方,多項式時間アルゴリズムは,路や閉路,木といった限られたクラスにしか知られておらず,木に対するアルゴリズムの計算量も 10 年以上 O(Δ4.5n) 時間であった (ただし,Δ はグラフの最大次数,n は木の頂点数).この計算量は最近になって O(min{n1.75, Δ1.5n}) 時間へと改善されたが,線形時間で解けるかどうかは未解決であった.本論文では,これを解決する木の L(2, 1) -ラベリングに対する線形時間アルゴリズムを提案する.An L(2, 1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f (x)− f (y)| ≥ 2 if x and y are adjacent and |f (x)− f (y)| ≥ 1 if x and y are at distance 2, for all x and y in V(G). A k-L(2, 1)-labeling is an L(2, 1)-labeling f : V(G) → {0, . . . , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ4.5n) for more than a decade, and an O(min{n1.75, Δ1.5n})-time algorithm has appeared recently, where Δ is the maximum degree of T and n = |V(T)|, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem for L(2, 1)-labeling of trees by establishing a linear time algorithm.

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

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

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2009 巻   頁: 78-79   2009年9月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  156. An O(n(1.75)) algorithm for L(2,1)-labeling of trees 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    THEORETICAL COMPUTER SCIENCE   410 巻 ( 38-40 ) 頁: 3702-3710   2009年9月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2009.04.025

    Web of Science

  157. RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)

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

    情報科学技術フォーラム講演論文集   8 巻 ( 1 ) 頁: 43-50   2009年8月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  158. メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション   109 巻 ( 54 ) 頁: 9-12   2009年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    研究報告アルゴリズム(AL)   2009 巻 ( 7 ) 頁: 1-8   2009年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    MAXMINO という無向グラフの向き付け問題の一種について考える.無向枝重みつきグラフの向き付けを与えることにより,重み付き出次数を定義する (枝重みは正整数であるとする).この問題は,グラフ中の最小重み付き出次数を最大化する問題である.本研究ではまず,MAXMINO は枝重みを {1 , 2} に限定し,かつ各頂点の (重みなし) 次数が高々 3,さらにグラフが平面二部であるような場合でも強 NP 困難であり,P= NP でない限り,任意の定数 E > 0 に対して多項式時間では 2 - E 近似不可能であることを示す.次にすべての枝重みが 1 である場合には,多項式時間で解くことができることを示す.これにより,枝重みが wmin よりも大きい枝数が O (log n)であるときにも,多項式時間で解くことができる.さらに,この手法により MAXMINO に対する単純な wmax / wmin 近似多項式時間アルゴリズムを得ることができる (wmax,wmin はそれぞれ枝重みの最大値,最小値).最後に,入力グラフがカクタスである場合にも MAXMINO は多項式時間で解くことができることを示す.We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 - E for any constant E > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax / wmin -approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph.

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1649 巻   頁: 160-164   2009年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  163. DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths

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

    電子情報通信学会総合大会講演論文集   2009 巻 ( 1 ) 頁: "S-35"-"S-36"   2009年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

  164. 証明書分散問題の近似可能性について

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

    研究報告アルゴリズム(AL)   2009 巻 ( 18 ) 頁: 49-56   2009年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    証明書分散問題(Minimum Certificate Dispersal Problem, MCD)とは,グラフGと要求集合Rが与えられたときに,Rに含まれるすべての要求を満たすよう各ノードにGの辺を割り当て,各ノードに割り当てられる辺の総数を最小化する問題である.要求とはグラフG上の異なる2つのノードの順序対で表され,要求(u, v)を満たすにはノードu, vに割り当てる辺の和集合にGにおけるuからvへの経路が含まれる必要がある.MCDは与えられるグラフが強連結の場合においてもNP-困難であることが既に示されている.本研究では,MCDの近似可能性について議論する.まず,強連結グラフにおいてMCDの近似率の下界がOmega(log n)(nはGのノード数)であることを示し,さらに任意のグラフにおけるMCDに対する多項式時間O(log n)-近似アルゴリズムが構成可能であることを示す.また,既存研究において多項式時間2-近似アルゴリズムであると評価されていたアルゴリズムが,無向グラフを入力とするMCDに対しては多項式時間3/2-近似アルゴリズムであることを示す.Assume that G is a graph and that R is a set of requests which is represented by a reachable ordered pair of nodes in G. The problem discussed in this paper requires us to assign edges to each node such that all requests in R are satisfied and the total number of edges all nodes have is minimized for a given G and R. To satisfy a request (u, v), a set of assigned edges to u and v must contain a path from u to v in G. This problem is called the Minimum Certificate Dispersal problem (MCD) and is NP-hard even if the input graph is restricted to a strongly connected one. In this paper, we consider approximability of MCD. We clarify an optimal approximability / inapproximability bound in terms of order: we prove the approximation ratio of MCD for strongly connected graphs is Omega (log n) and MCD has a polynomial time approximation algorithm whose factor is O(log n) (n is the number of nodes in G). In addition, we prove that when a given graph is restricted to an undirected graph, the MCD algorithm proposed in [11] guarantees 3/2 approximation ratio.

  165. Drawing Borders Efficiently

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

    Theory of Computing Systems   44 巻 ( 2 ) 頁: 230-244   2009年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.

  166. Drawing Borders Efficiently 査読有り

    Iwama Kazuo, Miyano Eiji, Ono Hirotaka

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00224-008-9117-y

    Web of Science

  167. 頻出属性検出階層型ストリームアルゴリズム

    溝口 隆, 山下 雅史, 小野 廣隆

    電気関係学会九州支部連合大会講演論文集   2009 巻 ( 0 ) 頁: 62-62   2009年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    通信ネットワークをノードとエッジと情報源を使って表す.ここで,ノード間の接続は多段階層化されており,根を最上位として,高さiのノード全体を第i層とする.データは情報源から最下位層のノードに対して与えられ,上位層に対しての一方向のみに送られる.ただし,各上位層のあるノードが単位時間当たり受け取ることができる情報の量は最下位層のあるノードが単位時間当たり受け取ることができる量と同じであるとする.本研究はこのような条件と各ノードのメモリを制限した場合に,情報源から得られた全てのデータの中で頻出したデータを最上位のノードが検出するためのストリームアルゴリズムの設計と解析である.

  168. Graph Orientation to Maximize the Minimum Weighted Outdegree 査読有り

    Asahiro Yuichi, Jansson Jesper, Miyano Eiji, Ono Hirotaka

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  169. Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG 査読有り

    Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION   5532 巻   頁: 98-107   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  170. Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem 査読有り

    Izumi Tomoko, Izumi Taisuke, Ono Hirotaka, Wada Koichi

    COMPUTING AND COMBINATORICS, PROCEEDINGS   5609 巻   頁: 56-+   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  171. A Linear Time Algorithm for L(2,1)-Labeling of Trees 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHMS - ESA 2009, PROCEEDINGS   5757 巻   頁: 35-+   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  172. 高速復元可能な接尾辞配列圧縮法

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

    電気関係学会九州支部連合大会講演論文集   2009 巻 ( 0 ) 頁: 58-58   2009年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    大規模データに対する高速な文字列検索は接尾辞配列 (SA) を用いて実現できるが, SAには多くの容量が必要になってしまう. SAを圧縮する様々な方法が提案されているが, 本論文では出現頻度の高いフレーズの検索が既存の圧縮法に比べて性能が良いような圧縮方法を提案する. 提案手法では, SAを大きさSのブロックに分割し, そのブロック内でソートを行い, 差分を取ったものを保存し, 検索時は差分からソート後のSAを取り戻し, 区間S内を全て逐次的に検索する. 最終的には実験により特に検索フレーズの頻度が高い場合, 多くの入力データで提案手法の性能が既存の方法より優れていることを示す.

  173. 全二分木の簡潔な表現

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

    電気関係学会九州支部連合大会講演論文集   2009 巻 ( 0 ) 頁: 59-59   2009年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    検索などに用いる順序木にはLOUDS, BP, DFUDSなどの簡潔表現が提案されている。これらはノード数nの順序木を表現する情報理論的下限2n-Θ(lgn)ビットにかなり近いものである。これらにo(n)ビットの補助データ構造を追加することで定数時間操作をサポートすることができる。簡潔表現としては他にTree Covering(TC)というのも存在する。本発表では順序木の中でもPaCB木などで用いられる全二分木に焦点を当て、これに対する簡潔データ構造を提案する。このデータ構造はDFUDSを基本としてTCを応用している。サイズはn+o(n)ビットとなり全二分木の情報理論的下限に近くなっている。

  174. 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性

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

    電気関係学会九州支部連合大会講演論文集   2009 巻 ( 0 ) 頁: 61-61   2009年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    ChienとSinclairは, 非協力対称渋滞ゲームにおける分散的なローカルダイナミクスによって, プレイヤー数n, プレイヤーの遷移への動機を制限する係数α, 辺の遅延関数の増加を制限する係数εの多項式回数以下の遷移ステップ数で近似的ナッシュ均衡状態を実現できることを示した.本論文は, その結果を拡張し, 分散的なコスト計算において個々のプレイヤーが他のプレイヤーの戦略についてある種の不完全な情報しか持たない場合にも同様の遷移回数によって必ず遷移を収束させることができる場合があるということを示し, そのために必要十分な条件について考察する.

  175. Route-Enabling Graph Orientation Problems 査読有り

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

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   5878 巻   頁: 403-+   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  176. How to Design a Linear Cover Time Random Walk on a Finite Graph 査読有り

    Nonaka Yoshiaki, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS   5792 巻   頁: 104-+   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  177. A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems 査読有り

    Ando Ei, Ono Hirotaka, Yamashita Masafumi

    STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, PROCEEDINGS   5792 巻   頁: 89-103   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  178. Speeding Up Local-Search Type Algorithms for Designing DNA Sequences under Thermodynamical Constraints 査読有り

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

    DNA COMPUTING   5347 巻   頁: 168-178   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

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

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

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2008 巻   頁: 308-309   2008年9月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

    情報科学技術フォーラム講演論文集   7 巻 ( 1 ) 頁: 5-6   2008年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

    情報処理学会研究報告バイオ情報学(BIO)   2008 巻 ( 58 ) 頁: 63-66   2008年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    ゲノム配列から,ある機能発現に関わる遺伝子を発見したいという要望がある.このような遺伝子は対象となるゲノム配列集合においてエラーを含んだ形で頻出する配列パターンの形をとることがしばしばある.本研究では,エラーを含む文字列集合から,ある長さの頻出部分文字列パターンを高速に全列挙するアルゴリズムを提案する.エラーの影響から通常のパターン列挙と異なり,入力文字列には現れないパターンも列挙の対象となる.提案手法ではパターン頻出性の必要条件を利用して最小限の候補パターンをハッシュ格納することにより,高速な全列挙を実現する.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.

  182. 最小重み負荷分散枝被覆について

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

    情報処理学会研究報告アルゴリズム(AL)   2008 巻 ( 49 ) 頁: 33-40   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    無向グラフ G=(V E)に対し,V の全ての点を被覆するような枝集合のことを枝被覆と呼ぶ.最小の枝被覆はスターグラフの集合の形をとり,また多項式時間で得られることが知られている.以前著者らは,負荷分散枝被覆問題,すなわち枝被覆が与えるスターグラフの中心頂点の次数が均等化されたような枝被覆を求める問題を考え,これを求める O(n1/2m log△)時間アルゴリズムを提案している.本論文では,枝に重みが付加されたグラフに対し最小重みの負荷分散枝被覆を求める問題について考える.最適解に対する特徴づけとしてある性質を持ったパス構造の存在性の形で与え,それに基づいた O(n3m)時間アルゴリズムを与える.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(n1/2m log△)-time polynomial time algorithm, where n, m and A 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(n3m)-time algorithm.

  183. グラフ上の線形 Cover Time ランダムウォーク実現の必要条件

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション   108 巻 ( 29 ) 頁: 33-35   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    有限グラフ上のランダムウォークとは,グラフ上に置かれた粒子が,その隣接点へとある確率にしたがってランダムに遷移するモデルである.ランダムウォークの速さの指標として,cover timeがある.これはある頂点を出発した粒子が,全ての頂点を訪問するために要する遷移数の期待値である.本研究の目的は,グラフが与えられたときよりcover timeの小さなランダムウォークを設計することである.本発表では,n頂点からなるグラフに対してcover timeがO(n)であるランダムウォークを設計可能であるための必要条件を示す.

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

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

    数理解析研究所講究録   1599 巻   頁: 182-188   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1599 巻   頁: 27-34   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1599 巻   頁: 57-64   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1599 巻   頁: 73-78   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1599 巻   頁: 127-132   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1599 巻   頁: 141-147   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1599 巻   頁: 170-175   2008年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  191. 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ

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

    情報処理学会研究報告アルゴリズム(AL)   2008 巻 ( 24 ) 頁: 43-50   2008年3月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    辺重みつき無向グラフが与えられ,辺の向き付けを求める問題 MMO を考える.MMO の目的は重みつき出次数の最大値を最小化することである.MMO は木に対してはΡ,平面二部グラフに対しては強 ΝΡ- 困難,一般のグラフに対してはNP- 困難であることが,過去の研究により知られている.しかし,これらのグラフクラス間には隔たりがあり,困難さの境界が厳密でない本稿の目的は,MMO の困難さの境界を明らかにすることであり,カクタス(木はカクタスの部分クラス)に対しては Ρ,多重辺を持つ外平面グラフや直並列グラフに対しては弱ΝΡ- 困難,平面グラフと二部グラフに対しては強ΝΡ- 困難であることを示す.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 Ρfor trees, weak .ΝΡ- hard for planar bipartite graphs, and strong ΝΡ- 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 Ρ for cactuses, (ii) weakly ΝΡ- hard for multi outerplanar graphs and series-parallel graphs, and also (iii) strongly ΝΡ-hard for planar graphs and bipartite graphs.

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

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

    電子情報通信学会総合大会講演論文集   2008 巻 ( 1 ) 頁: "S-19"-"S-20"   2008年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

  193. メトロポリス・ヘイスティングアルゴリズムに基づくO(n2)到達時間ランダムウォーク

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

    電気関係学会九州支部連合大会講演論文集   2008 巻 ( 0 ) 頁: 178-178   2008年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

    グラフ上のランダムウォークにおいて,隣接頂点への遷移確率をメトロポリス・ヘイスティングアルゴリズムに基づいて定義することで,到達時間がO(n^2)となるランダムウォークを実現することが出来る.ここで,nはグラフの頂点数でる.また,到達時間とはある頂点を出発し,別のある頂点へ達するまでに要する遷移数の期待値である.

  194. Deductive Inference for the Interiors and Exteriors of Horn Theories 査読有り

    Makino Kazuhisa, Ono Hirotaka

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   5369 巻   頁: 390-+   2008年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  195. The Balanced Edge Cover Problem 査読有り

    Harada Yuta, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   5369 巻   頁: 246-257   2008年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  196. Dynamic neighborhood searches for thermodynamically designing DNA sequence 査読有り

    Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   4848 巻   頁: 130-+   2008年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

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

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

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

  198. The space complexity of the leader election in anonymous networks 査読有り

    Ando Ei, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

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

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  199. An O(n<(1.75)) algorithm for L(2,1)-labeling of trees 査読有り

    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi

    ALGORITHM THEORY - SWAT 2008   5124 巻   頁: 185-+   2008年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

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

    小野 廣隆, 貞廣 泰造

    電子情報通信学会技術研究報告. COMP, コンピュテーション   107 巻 ( 258 ) 頁: 19-24   2007年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

    牧野 和久, 小野 廣隆

    電子情報通信学会技術研究報告. COMP, コンピュテーション   107 巻 ( 127 ) 頁: 33-39   2007年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

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

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション   107 巻 ( 73 ) 頁: 43-50   2007年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

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

  203. ブックマーク問題の近似について

    朝廣 雄一, 宮野 英次, 小野 廣隆, 村田 俊英

    電子情報通信学会技術研究報告. COMP, コンピュテーション   107 巻 ( 73 ) 頁: 1-6   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    ハイパーリンクの集合Eで連結されたウェブページの集合Vを表した根付き有向非巡回グラフG=(V,E)を考える.それぞれのノードvは,ユーザがノードvを閲覧するアクセス頻度を持っている.アクセスコストは,根ノードrからあるノードvに到達するためのステップ数の期待値で定義される.ブックマークは,グラフGの根ノードrに付加するショートカットリンクであり,アクセスコストを小さくする効果がある.ブックマーク問題は,アクセスコストを最も改善するようなブックマーク集合を求める問題である.本稿では,ブックマーク問題に対する(1-1/e)近似アルゴリズムを示す.またNP&subE;DTIME(N^<o(loglogN)>)を満たさない場合には,(1-1/e)よりも良い近似比を持つ多項式時間のアルゴリズムは存在しないことを示す.ここで,Nは入力サイズを表している.

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

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

    数理解析研究所講究録   1554 巻   頁: 269-275   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 101-108   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 139-144   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 202-209   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 238-242   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 243-249   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 250-257   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

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

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

    数理解析研究所講究録   1554 巻   頁: 264-268   2007年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  212. Graph orientation algorithms to minimize the maximum outdegree 査読有り

    Asahiro Yuichi, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   18 巻 ( 2 ) 頁: 197-215   2007年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  213. k-集合合意問題を解く故障検知器

    坂田 敦, 小野 廣隆, 定兼 邦彦, 山下 雅史

    電子情報通信学会技術研究報告. COMP, コンピュテーション   106 巻 ( 566 ) 頁: 1-6   2007年3月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    故障検知器は分散システムにおいて各プロセスごとに備わった他のプロセスの故障状況を教えるオラクルである.故障が起きる際には非可解とされている問題に対して,どの程度の故障検知能力を有する故障検知器が備わればそれが可解となるかが広く研究されている.特に,問題を解くために必要十分な最弱の故障検知器が重要である.本稿では重要な分散問題の1つである合意問題を一般化したk-集合合意問題を解く故障検知器を考察する.合意問題に対する最弱の故障検知器であるクラス(Ω,Σ)を拡張したクラス(k-Ω,Σ)と(Ω,Σ_k)を定義し,プロセスの故障数が任意の環境下でこれらの検知器を用いてk-集合合意問題を解けることを示す.また,関連研究において同様にk-集合合意問題を解くと示されている故障検知器との強弱関係の比較を行う.

  214. 移動物体回収問題

    朝廣 雄一, 小野 廣隆, 宮野 英次, 山下 雅史

    電子情報通信学会誌 = THE JOURNAL OF THE INSTITUTE OF ELECTRONICS, INFOMATION AND COMMUNICATION ENGINEERS   90 巻 ( 3 ) 頁: 245-247   2007年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

  215. スケールフリーグラフにおける次数情報を用いた頂点探索

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

    電気関係学会九州支部連合大会講演論文集   2007 巻 ( 0 ) 頁: 95-95   2007年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

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

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

    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS   4508 巻   頁: 167-+   2007年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  217. 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比

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

    電気関係学会九州支部連合大会講演論文集   2007 巻 ( 0 ) 頁: 85-85   2007年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

  218. 局所探索法に基づく熱力学的DNA配列設計

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

    電気関係学会九州支部連合大会講演論文集   2007 巻 ( 0 ) 頁: 93-93   2007年

     詳細を見る

    掲載種別:研究論文(学術雑誌)  

  219. On approximation of bookmark assignments 査読有り

    Asahiro Yuichi, Miyano Eiji, Murata Toshihide, Ono Hirotaka

    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS   4708 巻   頁: 115-+   2007年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  220. Drawing borders efficiently 査読有り

    Iwama Kazuo, Miyano Eiji, Ono Hirotaka

    FUN WITH ALGORITHMS, PROCEEDINGS   4475 巻   頁: 213-+   2007年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  221. How to collect balls moving in the Euclidean plane 査読有り

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

    DISCRETE APPLIED MATHEMATICS   154 巻 ( 16 ) 頁: 2247-2262   2006年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2006.04.020

    Web of Science

  222. 動的近傍操作を用いたDNA塩基配列設計

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション   106 巻 ( 63 ) 頁: 47-54   2006年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    近年,DNA塩基配列集合を利用したナノコンピューティング・ナノテクノロジーが注目されている.これらの技術に用いられる塩基配列集合は,利用目的に応じた制約を満たす必要がある.いくつかの制約は組合せ的であるので,本論文では塩基配列集合問題を組合せ最適化問題と捉える.さらに,他の制約より組合せ的なオーバーラップ指標に着目し,局所探索法に基づくアルゴリズムを提案する.このアルゴリズムでは組合せ的制約を局所探索法で充足させるために,可変近傍探索法・可変深度探索近傍法と呼ばれる動的近傍操作を採用する.計算機実験において,提案手法は同様の制約を満たす他の手法と同等以上の配列集合の設計に成功した.

  223. 隠れマルコフモデルを用いたDNA配列設計

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション   106 巻 ( 63 ) 頁: 39-46   2006年5月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)  

    DNAコンピューティングとは,DNA同士の反応過程を計算として見なした新しい計算パラダイムである.DNAコンピューティングでは,計算に使用するDNA分子の塩基配列を設計することが重要な研究テーマのひとつとなっている.DNA分子が意図したように反応するには,様々な制約をできるだけ満たす配列を準備する必要がある.このため従来様々な塩基配列の設計手法が研究されてきたが,本研究では隠れマルコフモデルを用いた配列設計を提案する.隠れマルコフモデルはマルコフ過程を利用した確率モデルである.本論文では,試験的な配列設計として行った,DNAのもつ最小自由エネルギーが小さい配列の設計の実験と結果について述べる.

  224. DNA sequence design by dynamic neighborhood searches 査読有り

    Kawashimo Suguru, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   4287 巻   頁: 157-+   2006年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  225. Forest search: A paradigm for faster exploration of scale-free networks 査読有り

    Kurumida Yuichi, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    PARALLEL AND DISTRIBUTED PROCESSING AND APPLICATIONS   4330 巻   頁: 39-+   2006年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

  226. A probabilistic model of the DNA conformational change 査読有り

    Shiozaki Masashi, Ono Hirotaka, Sadakane Kunihiko, Yamashita Masafumi

    DNA COMPUTING   4287 巻   頁: 274-+   2006年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Web of Science

▼全件表示

MISC 20

  1. 交差グラフモデルの下での最適シフト区間のためのアルゴリズム【JST・京大機械翻訳】|||

    HONORATO DROGUETT Nicolas, KURITA Kazuhiro, HANAKA Tesshu, ONO Hirotaka  

    電子情報通信学会技術研究報告(Web)123 巻 ( 325(COMP2023 16-27) )   2023年

     詳細を見る

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

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

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

     詳細を見る

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

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

    ゲームプログラミングワークショップ2021論文集 ( 2021 ) 頁: 130 - 137   2021年11月

     詳細を見る

    記述言語:日本語  

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

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

    情報処理学会ゲーム情報学研究会 研究報告2021-GI-46 巻 ( 14 ) 頁: 1 - 8   2021年6月

     詳細を見る

    担当区分:最終著者   記述言語:日本語   掲載種別:機関テクニカルレポート,技術報告書,プレプリント等  

    J-GLOBAL

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

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

    日本OR学会第48回中部支部研究発表会   2021年3月

     詳細を見る

    担当区分:最終著者   記述言語:日本語  

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

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

    日本OR学会第48回中部支部研究発表会   2021年3月

     詳細を見る

    担当区分:最終著者   記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

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

    日本OR学会第48回中部支部研究発表会   2021年3月

     詳細を見る

    記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

  8. Hedonic Seat Arrangement Problems 招待有り

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

     詳細を見る

    記述言語:英語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

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

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

     詳細を見る

    記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

    J-GLOBAL

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

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

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

     詳細を見る

    担当区分:最終著者   記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

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

    2020年度 冬のLAシンポジウム   2021年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

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

    2020年度 冬のLAシンポジウム   2021年2月

     詳細を見る

    記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

    木谷裕紀, 小野廣隆  

    システム/制御/情報65 巻 ( 10 )   2021年

     詳細を見る

  14. 組合せゲームに対するアルゴリズム論的アプローチ (「組合せゲーム理論」特集号)

    木谷 裕紀, 小野 廣隆  

    システム・制御・情報 = Systems, control and information : システム制御情報学会誌65 巻 ( 10 ) 頁: 415 - 420   2021年

     詳細を見る

    記述言語:日本語   出版者・発行元:システム制御情報学会  

    CiNii Books

  15. L(p,1)-ラベリング問題に対する固定パラメータアルゴリズム

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

    信学技報, COMP2020-24120 巻 ( 276 ) 頁: 30 - 32   2020年12月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:機関テクニカルレポート,技術報告書,プレプリント等  

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

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

    信学技報, COMP2020-21120 巻 ( 276 ) 頁: 24 - 27   2020年12月

     詳細を見る

    記述言語:英語   掲載種別:機関テクニカルレポート,技術報告書,プレプリント等  

    その他リンク: https://dl.acm.org/doi/10.5555/3535850.3536053

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

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

    第16回情報科学ワークショップ   頁: 1616 - 1617   2020年9月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

    その他リンク: https://dl.acm.org/doi/10.5555/3535850.3536053

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

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

    第16回情報科学ワークショップ   2020年9月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

    伊藤雅士, 小野廣隆  

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

     詳細を見る

    担当区分:最終著者   記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

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

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

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

     詳細を見る

▼全件表示

講演・口頭発表等 104

  1. 超スマート社会時代のアルゴリズム工学 招待有り

    小野廣隆

    2024年度(第59回)日本OR学会九州支部総会・講演会  2024年3月23日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(招待・特別)  

  2. An Edit Model and Algorithms for Achieving Properties on Intersection Graphs

    Honorato Droguett Nicolas, Kurita Kazuhiro, Hanaka Tesshu, Ono Hirotaka

    第197回AL研究発表会  2024年3月21日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  3. ラプラシアン行列の固有値を用いた木幅の下界

    儀間 達也, 土中 哲秀, 野呂 浩平, 小野 廣隆, 大舘 陽太

    第197回AL研究発表会  2024年3月21日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  4. グラフ分解に基づく高性能なビール路クエリシステム

    杉山 康恭, 土中 哲秀, 小野 廣隆, 定兼 邦彦

    第197回AL研究発表会  2024年3月21日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  5. YOMENの最適質問数

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

    第197回AL研究発表会  2024年3月21日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  6. あるパターンにおけるパスドミニアリングのゲーム値と必勝判定について

    石垣尚斗, 吉渡叶, 小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第18回研究集会  2024年3月15日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  7. 競技大会におけるバイトニックソート的順位付け方式

    山本晃司, 栗田和宏, 小野廣隆

    組合せゲーム・パズル(CGP) プロジェクト 第18回研究集会  2024年3月16日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  8. Hardness of Uniquifying Minimum Vertex Covers and Minimum Dominating Sets under Pre-assignments

    堀山 貴史, 小林 靖明, 小野 廣隆, 脊戸 和寿, 鈴木 琉

    2024年電子情報通信学会総合大会 COMP-AFSA 学生シンポジウム  2024年3月5日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  9. グラフ分解に基づく高性能なビール路クエリシステム

    杉山 康恭, 土中 哲秀, 小野 廣隆, 定兼 邦彦

    2024年電子情報通信学会総合大会 COMP-AFSA 学生シンポジウム  2024年3月6日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  10. ラプラシアン行列の固有値を用いた木幅の下界とその改善

    儀間 達也, 土中 哲秀, 野呂 浩平, 小野 廣隆, 大舘 陽太

    2024年電子情報通信学会総合大会 COMP-AFSA 学生シンポジウム  2024年3月6日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  11. グラフ分解に基づく高性能なビール路クエリシステム

    杉山康恭, 小野廣隆, 土中哲秀, 定兼邦彦

    日本オペレーションズ・リサーチ学会 第 51 回中部支部研究発表会・特別講演会  2024年3月2日 

     詳細を見る

    開催年月日: 2024年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  12. An Edit Model and Algorithms for Achieving Properties on Intersection Graphs

    オノラト ドロゲット ニコラス, 栗田 和宏, 土中 哲秀, 小野 廣隆

    2023年度 冬の LA シンポジウム  2024年2月20日 

     詳細を見る

    開催年月日: 2024年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  13. ラプラシアン行列の固有値に関する木幅の下界とそのさらなる改善

    儀間 達也, 土中 哲秀, 野呂 浩平, 小野 廣隆, 大舘 陽太

    2023年度 冬の LA シンポジウム  2024年2月20日 

     詳細を見る

    開催年月日: 2024年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  14. グラフ分解に基づく高性能なビール路クエリシステム

    杉山 康恭, 土中 哲秀, 小野 廣隆, 定兼 邦彦

    2023年度 冬の LA シンポジウム  2024年2月20日 

     詳細を見る

    開催年月日: 2024年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  15. YOMENの最適質問数

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

    2023年度 冬のLAシンポジウム  2024年2月19日 

     詳細を見る

    開催年月日: 2024年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  16. Algorithms for Optimally Shifting Intervals under Intersection Graph Models

    Honorato Droguett Nicolas, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono

    コンピュテーション研究会(COMP)2023-12  2023年12月22日 

     詳細を見る

    開催年月日: 2023年12月

    記述言語:英語  

  17. Algorithms for Optimally Shifting Intervals under Intersection Graph Models

    Nicolás Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono

    日本オペレーションズ・リサーチ学会 九州支部 九州地区におけるOR若手研究交流会 2023湯布院  2023年10月29日 

     詳細を見る

    開催年月日: 2023年10月

    記述言語:英語   会議種別:口頭発表(一般)  

  18. コード類似を利用した自然な楽曲の変容

    松下昂世, 栗田和宏, 小野廣隆

    日本オペレーションズ・リサーチ学会 九州支部 九州地区におけるOR若手研究交流会 2023湯布院  2023年10月29日 

     詳細を見る

    開催年月日: 2023年10月

    記述言語:日本語  

  19. Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

    Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

    コンピュテーション研究会(COMP)2023-10  2023年10月25日 

     詳細を見る

    開催年月日: 2023年10月

    記述言語:英語   会議種別:口頭発表(一般)  

  20. An improved spectral lower bound of treewidth

    Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi

    The 25th Indonesia-Japan Conference on Discrete and Computational Geometry, Graphs, and Games  2023年9月24日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:英語   会議種別:口頭発表(一般)  

  21. Upper and Lower Bounds on the Optimal Questions for YOMEN

    Kouki Hirano, Hironori Kiya, Tesshu Hanaka, Hirotaka Ono

    The 25th Indonesia-Japan Conference on Discrete and Computational Geometry, Graphs, and Games  2023年9月22日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:英語   会議種別:口頭発表(一般)  

  22. The Price of Stability of Fractional Hedonic Games on Graphs with Many Triangles

    Tesshu Hanaka, Airi Ikeyama, Hirotaka Ono

    The 25th Indonesia-Japan Conference on Discrete and Computational Geometry, Graphs, and Games  2023年9月22日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:英語   会議種別:口頭発表(一般)  

  23. Critical Sets of n-omino Sudoku

    Takashi Horiyama, Tonan Kamata, Hironori Kiya, Hirotaka Ono, Takumi Shiota, Ryuhei Uehara, Yushi Uno

    The 25th Indonesia-Japan Conference on Discrete and Computational Geometry, Graphs, and Games  2023年9月22日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:英語   会議種別:口頭発表(一般)  

  24. Algorithms for Optimally Shifting Intervals under Intersection Graph Models

    Nicolás Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono

    第19回情報科学ワークショップ  2023年9月13日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

  25. YOMENの最適質問数

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

    第19回情報科学ワークショップ  2023年9月13日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

  26. 離合コスト下でのパス計画ゲームの計算量

    関口裕也, 土中哲秀, 小野廣隆

    第19 回情報科学ワークショップ  2023年9月13日 

     詳細を見る

    開催年月日: 2023年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

  27. Optimally shifting intervals under intersection graph models

    Nicolás Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono

    2023年度 夏の LA シンポジウム  2023年7月4日 

     詳細を見る

    開催年月日: 2023年7月

    記述言語:英語   会議種別:口頭発表(一般)  

  28. SPQR木を利用したビール路問題への解法

    杉山 康恭, 土中 哲秀, 小野 廣隆, 定兼 邦彦

    2023年度 夏の LA シンポジウム  2023年7月3日 

     詳細を見る

    開催年月日: 2023年7月

    記述言語:日本語   会議種別:口頭発表(一般)  

  29. 続・ラプラシアン行列の固有値に関する木幅の下界とその改善

    儀間 達也, 土中 哲秀, 野呂 浩平, 小野 廣隆, 大舘 陽太

    2023年度 夏のLA シンポジウム  2023年7月3日 

     詳細を見る

    開催年月日: 2023年7月

    記述言語:日本語   会議種別:口頭発表(一般)  

  30. 閾値グラフ上の一般化辺しりとり

    江藤 宏, 土中 哲秀, 木谷 裕紀, 小野 廣隆

    2023年度 夏の LA シンポジウム  2023年7月5日 

     詳細を見る

    開催年月日: 2023年7月

    記述言語:日本語   会議種別:口頭発表(一般)  

  31. Collecting Balls on a Line by Robots with Limited Energy

    Nicolás Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Yota Otachi, Hirotaka Ono

    The 23rd Japan–Korea Joint Workshop on Algorithms and Computation  2023年6月24日 

     詳細を見る

    開催年月日: 2023年6月

    記述言語:英語   会議種別:口頭発表(一般)  

  32. Structural Parameterizations of Vertex Integrity

    Ryota Murai, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Hirotaka Ono, Yota Otachi

    The 23rd Japan–Korea Joint Workshop on Algorithms and Computation  2023年6月25日 

     詳細を見る

    開催年月日: 2023年6月

    記述言語:英語   会議種別:口頭発表(一般)  

  33. On a spectral lower bound of treewidth

    Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi

    The 23rd Japan–Korea Joint Workshop on Algorithms and Computation  2023年6月25日 

     詳細を見る

    開催年月日: 2023年6月

    記述言語:英語   会議種別:口頭発表(一般)  

  34. Reallocation Problems with Minimum Completion Time 招待有り

    コンピュテーション研究会(COMP)2023-05  2023年5月10日 

     詳細を見る

    開催年月日: 2023年5月

    記述言語:英語   会議種別:口頭発表(招待・特別)  

  35. 最長ラン部分文字列問題に対する近似アルゴリズム

    朝廣 雄一, 江藤 宏, Mingyang Gong, Jesper Jansson, Guohui Lin, 宮野 英次, 小野 廣隆, 田中 駿一

    第193回情報処理学会アルゴリズム研究会  2023年5月11日 

     詳細を見る

    開催年月日: 2023年5月

    記述言語:日本語   会議種別:口頭発表(一般)  

  36. ぷよぷよマッピング問題 招待有り

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

    2023年電子情報通信学会総合大会 COMP-AFSA 学生シンポジウム  2023年3月10日 

     詳細を見る

    開催年月日: 2023年3月

    記述言語:日本語   会議種別:口頭発表(招待・特別)  

  37. 辺ケイレスに対する必勝判定アルゴリズムの計算量解析

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

    2023年電子情報通信学会総合大会 COMP-AFSA 学生シンポジウム  2023年3月10日 

     詳細を見る

    開催年月日: 2023年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  38. グループ支配集合問題のグラフ構造パラメータに関する計算量

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

    2023年電子情報通信学会総合大会 COMP-AFSA 学生シンポジウム  2023年3月10日 

     詳細を見る

    開催年月日: 2023年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  39. 2種の中継器による端末接続問題

    杜文博, 小野廣隆, 土中哲秀

    日本OR学会第50回中部支部研究発表会  2023年3月4日 

     詳細を見る

    開催年月日: 2023年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  40. 片切れ交換方式を用いたLPガス容器交換計画に関するケーススタディ

    岩田弘樹, 若原達朗, 高田陽介, 胡艶楠, 小野廣隆, 橋本英樹, 柳浦睦憲

    日本OR学会第50回中部支部研究発表会  2023年3月4日 

     詳細を見る

    開催年月日: 2023年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

  41. Collecting Balls on a Line by Robots with Limited Energy

    2022年度 冬のLAシンポジウム  2023年1月31日 

     詳細を見る

    開催年月日: 2023年1月 - 2023年2月

    記述言語:英語   会議種別:口頭発表(一般)  

  42. 頂点インテグリティのパラメータ化計算量

    村井 亮太, 儀間 達也, 土中 哲秀, 小林 靖明, 小野 廣隆, 大舘 陽太

    2022 年度 冬の LA シンポジウム  2023年2月1日 

     詳細を見る

    開催年月日: 2023年1月 - 2023年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  43. 離合コスト下でのパス計画ゲームのナッシュ均衡

    関口 裕也, 土中 哲秀, 小野 廣隆

    2022 年度 冬の LA シンポジウム  2023年2月1日 

     詳細を見る

    開催年月日: 2023年1月 - 2023年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  44. 分数型ヘドニックゲームにおける最適提携構造の計算

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

    2022 年度 冬の LA シンポジウム  2023年1月30日 

     詳細を見る

    開催年月日: 2023年1月 - 2023年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  45. ラプラシアン行列の固有値に関する木幅の下界とその改善

    野呂 浩平, 儀間 達也, 土中 哲秀, 大舘 陽太, 小野 廣隆

    2022 年度 冬の LA シンポジウム  2023年1月31日 

     詳細を見る

    開催年月日: 2023年1月 - 2023年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  46. Sequentially Swapping Tokens: Further on Graph Classes

    コンピュテーション研究会(COMP)  2022年12月6日 

     詳細を見る

    開催年月日: 2022年12月

    記述言語:英語   会議種別:口頭発表(一般)  

  47. 「タイル返し」のPSPACE完全性

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

    第190回AL研究発表会  2022年11月18日 

     詳細を見る

    開催年月日: 2022年11月

    記述言語:日本語   会議種別:口頭発表(一般)  

  48. 離合コスト下でのパス計画ゲームのナッシュ均衡

    関口裕也, 土中哲秀, 小野廣隆

    第 18 回情報科学ワークショップ  2022年9月11日 

     詳細を見る

    開催年月日: 2022年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

  49. 2 種の中継器による端末接続問題

    杜文博, 土中哲秀, 小野廣隆

    第 18 回情報科学ワークショップ  2022年9月11日 

     詳細を見る

    開催年月日: 2022年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

  50. (色付き)辺ケイレスの計算量

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

    第 18 回情報科学ワークショップ  2022年9月 

     詳細を見る

    開催年月日: 2022年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

  51. 小直径グラフにおける距離制約付きラベリング問題のTSPへの帰着

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

    2022 年度 夏の LA シンポジウム  2022年7月 

     詳細を見る

    開催年月日: 2022年7月

    記述言語:日本語   会議種別:口頭発表(一般)  

  52. Grouped domination parameterized by vertex cover, twin cover, and beyond

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

    2022 年度 夏の LA シンポジウム  2022年7月 

     詳細を見る

    開催年月日: 2022年7月

    記述言語:英語   会議種別:口頭発表(一般)  

  53. Winner Determination Algorithms for Colored Arc Kayles

    Kanae Yoshiwatari, Hironori Kiya, Tesshu Hanaka, Hirotaka Ono

    第48回ゲーム情報学研究発表会  2022年7月 

     詳細を見る

    開催年月日: 2022年7月

    記述言語:英語   会議種別:口頭発表(一般)  

  54. ブロックグラフにおける分数型ヘドニックゲームの最適提携構造

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

    2022 年度 夏の LA シンポジウム  2022年7月 

     詳細を見る

    開催年月日: 2022年7月

    記述言語:日本語   会議種別:口頭発表(一般)  

  55. 売却可能スキーレンタル問題の競合比

    瀧塚 公太郎, 土中 哲秀, 小野 廣隆

    2022 年度 夏の LA シンポジウム  2022年7月 

     詳細を見る

    開催年月日: 2022年7月

    記述言語:日本語   会議種別:口頭発表(一般)  

  56. 小直径グラフにおける距離制約付きラベリング問題のTSPへの帰着

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

    最適化手法とアルゴリズム (SOMA) —未来を担う若手研究者の集い 2022—  2022年6月 

     詳細を見る

    開催年月日: 2022年6月

    会議種別:口頭発表(一般)  

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

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

    情報処理学会第47回GI研究発表会  2022年3月18日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    情報処理学会第47回GI研究発表会  2022年3月18日 

     詳細を見る

    開催年月日: 2022年3月

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

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

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

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

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

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

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

     詳細を見る

    開催年月日: 2022年3月

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

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

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

     詳細を見る

    開催年月日: 2022年3月

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

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

    2021年度 組合せ遷移の学⽣シンポジウム  2022年3月9日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    2021年度 組合せ遷移の学?シンポジウム  2022年3月9日 

     詳細を見る

    開催年月日: 2022年3月

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月8日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月7日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月7日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月7日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月8日 

     詳細を見る

    開催年月日: 2022年3月

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月7日 

     詳細を見る

    開催年月日: 2022年3月

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月7日 

     詳細を見る

    開催年月日: 2022年3月

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

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

    組合せゲーム・パズル(CGP) プロジェクト 第16回 研究集会  2022年3月7日 

     詳細を見る

    開催年月日: 2022年3月

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

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

    第49回日本OR学会中部支部研究発表会  2022年3月5日 

     詳細を見る

    開催年月日: 2022年3月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    第49回日本OR学会中部支部研究発表会  2022年3月5日 

     詳細を見る

    開催年月日: 2022年3月

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

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

    2021年度 冬のLAシンポジウム  2022年2月3日 

     詳細を見る

    開催年月日: 2022年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    2021年度 冬のLAシンポジウム  2022年2月1日 

     詳細を見る

    開催年月日: 2022年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    2021年度 冬のLAシンポジウム  2022年2月2日 

     詳細を見る

    開催年月日: 2022年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    2021年度 冬のLAシンポジウム  2022年2月2日 

     詳細を見る

    開催年月日: 2022年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    2021年度 冬のLAシンポジウム  2022年2月2日 

     詳細を見る

    開催年月日: 2022年2月

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

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

    2021年度 冬のLAシンポジウム  2022年2月3日 

     詳細を見る

    開催年月日: 2022年2月

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

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

    2021年度 冬のLAシンポジウム  2022年2月1日 

     詳細を見る

    開催年月日: 2022年2月

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

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

    2021年度 冬のLAシンポジウム  2022年2月2日 

     詳細を見る

    開催年月日: 2022年2月

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

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

    ゲームプログラミングワークショップ2021  2021年11月14日 

     詳細を見る

    開催年月日: 2021年11月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    ゲームプログラミングワークショップ2021  2021年11月14日 

     詳細を見る

    開催年月日: 2021年11月

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

     詳細を見る

    開催年月日: 2021年10月

    記述言語:英語   会議種別:口頭発表(一般)  

  86. 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日 

     詳細を見る

    開催年月日: 2021年10月

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

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

    コンピュテーション研究会  2021年10月23日 

     詳細を見る

    開催年月日: 2021年10月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    コンピュテーション研究会  2021年10月23日 

     詳細を見る

    開催年月日: 2021年10月

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

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

    関西支部 SSOR 2021   2021年10月16日 

     詳細を見る

    開催年月日: 2021年10月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    関西支部 SSOR 2021  2021年10月16日 

     詳細を見る

    開催年月日: 2021年10月

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

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

    第17回 情報科学ワークショップ  2021年9月13日 

     詳細を見る

    開催年月日: 2021年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    第17回 情報科学ワークショップ  2021年9月12日 

     詳細を見る

    開催年月日: 2021年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    第17回 情報科学ワークショップ  2021年9月12日 

     詳細を見る

    開催年月日: 2021年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    第17回 情報科学ワークショップ  2021年9月13日 

     詳細を見る

    開催年月日: 2021年9月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    第17回 情報科学ワークショップ  2021年9月13日 

     詳細を見る

    開催年月日: 2021年9月

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

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

    第17回 情報科学ワークショップ  2021年9月13日 

     詳細を見る

    開催年月日: 2021年9月

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

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

    第17回 情報科学ワークショップ  2021年9月12日 

     詳細を見る

    開催年月日: 2021年9月

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

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

    第17回 情報科学ワークショップ  2021年9月12日 

     詳細を見る

    開催年月日: 2021年9月

  99. 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日 

     詳細を見る

    開催年月日: 2021年9月

  100. 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日 

     詳細を見る

    開催年月日: 2021年9月

    記述言語:英語   会議種別:口頭発表(一般)  

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

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

    情報処理学会第46回GI研究発表会  2021年6月20日 

     詳細を見る

    開催年月日: 2021年6月

    記述言語:日本語   会議種別:口頭発表(一般)  

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

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

    日本オペレーションズ・リサーチ学会 九州支部 若手OR研究交流会 2020  2020年11月28日 

     詳細を見る

    開催年月日: 2020年11月

    記述言語:日本語   会議種別:口頭発表(一般)  

  103. ペア支配集合の頂点被覆によるパラメータ化アルゴリズム

    宇田 冴輝, 土中 哲秀, 小野 廣隆

    日本オペレーションズ・リサーチ学会 九州支部 若手OR研究交流会 2020  2020年11月28日 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

  104. Computational complexity of Turning Tiles 招待有り

    Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kaane Yoshiwatari

    Games at Mumbai 2024  2024年1月24日 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

▼全件表示

科研費 9

  1. 最適化計算型クエリーのためのプリプロセッシングアルゴリズム論

    研究課題/研究課題番号:21K19765  2021年7月 - 2024年3月

    科学研究費助成事業  挑戦的研究(萌芽)

    小野 廣隆

      詳細を見る

    担当区分:研究代表者 

    配分額:6110000円 ( 直接経費:4700000円 、 間接経費:1410000円 )

    本研究では最適化計算型クエリー+プリプロセッシングのための新たなアルゴリズム論を展開する.最適化計算型クエリーのプリプロセッシングには,付加する補助情報の量と最適化自体の計算量の関係, プリプロセッシングに要する計算量と最適化自体の計算量の関係等,各種のトレードオフ関係が存在する.これは個別に研究されてきたアルゴリズム理論上の諸問題が最適化計算型クエリーに対するプリプロセッシングという設定で融合することを意味する.本研究はこの新しい計算スキームにおける汎用的なアプローチを構築,各種のトレードオフ関係の評価体系の提案をするとともに,実装・評価を通した新たなアルゴリズム設計論の展開に挑戦する.

  2. 組合せ最適化問題に対する解の唯一化における計算複雑さの研究

    研究課題/研究課題番号:24K02898  2024年4月 - 2028年3月

    日本学術振興会  科学研究費助成事業  基盤研究(B)

    脊戸 和寿, 小野 廣隆, 長尾 篤樹, 小野 廣隆, 長尾 篤樹

      詳細を見る

    担当区分:研究分担者 

    数独をはじめとするパズルでは解盤面が唯一であることが重要である。しかし、唯一解をもつ盤面を生成することは、数独のサイズが大きくなると簡単ではないことが過去の研究で示されている。唯一解をもつインスタンスを生成することはパズルだけでなく、種々のアルゴリズムの解析などにおいて重要であり、本研究では組合せ最適化問題における解の唯一化の計算困難性を明らかにし、アルゴリズムの構築も行う。

  3. 超スマート社会時代のアルゴリズム工学 - パラメータ化近似均衡計算

    研究課題/研究課題番号:22H00513  2022年4月 - 2027年3月

    日本学術振興会  科学研究費助成事業  基盤研究(A)

    小野 廣隆, 柳浦 睦憲, 大舘 陽太, 脊戸 和寿, 土中 哲秀, 柳浦 睦憲, 大舘 陽太, 脊戸 和寿, 土中 哲秀

      詳細を見る

    担当区分:研究代表者 

    配分額:40820000円 ( 直接経費:31400000円 、 間接経費:9420000円 )

    均衡解は多主体最適化系における安定解であり,超スマート社会における混雑・衝突の予測・制御における鍵となる概念である.本研究では,これまで最適解発見を主な対象としていたアルゴリズム設計論の対象を均衡解発見へと発展・拡大する.通常の最適化がNP, coNPに属するのに対し均衡発見はΣ2, Π2といった多項式階層におけるより上位の計算量クラス,あるいは近傍探索におけるPLS, PPADといった計算クラスに属するため,従来型の最適化研究を超えた新たな計算量理論の展開が必要となる.本研究では,超スマート社会における基盤技術を提供する,パラメータ化計算量に基づく新たなアルゴリズム工学の確立を目指す.

  4. アルゴリズム基礎理論の追究・発展 国際共著

    研究課題/研究課題番号:20H05967  2020年11月 - 2025年3月

    日本学術振興会  科学研究費助成事業 学術変革領域研究(A)  学術変革領域研究(A)

    牧野 和久, 小野 廣隆, 定兼 邦彦, 河村 彰星, 玉置 卓, 瀧本 英二, 渋谷 哲朗, 小野 廣隆, 定兼 邦彦, 玉置 卓, 瀧本 英二, 渋谷 哲朗, 河村 彰星

      詳細を見る

    担当区分:研究分担者  資金種別:競争的資金

    配分額:260000円 ( 直接経費:200000円 、 間接経費:60000円 )

    本研究では,現在の高度情報化社会を駆動する「アルゴリズム」の基礎理論をさらに追及し,展開させること目的とする.P vs NP問題に代表されるように,アルゴリズム分野において未解決に残された部分は数多く存在する.一方,情報学,工学,農学,医学など多様な応用分野では,それぞれに特化したアルゴリズムが開発されている.それらアルゴリズムを飛躍的に進化させるためには,基礎理論の革新が必要不可欠な現状にある.
    本研究では,データ構造効率化法,離散構造解析法を行うこと,また,他の計画班と密接に連携を行うことで,アルゴリズム理論の革新を行う.
    本研究課題を大きく1.アルゴリズム研究(AL),2.データ構造研究(DS)に分ける形で取り組みそれぞれ研究成果を得た.以下1,2の各テーマで得られた結果を概観する.
    1.[最適化AL] 牧野は下限付き安定マッチング問題を下限の充足率最大化問題としてとらえ直しその近似比の上下界を与えた.小野はグラフ上の色付きトークンの再配置問題のNP完全性が,ある性質を満たすグラフ群において成立することを示し, また既存の多項式時間アルゴリズムの適用範囲を大幅に拡大した.[論理学的AL]牧野は,関係データベース等への応用のためキーホーン関数を定義した.その最小表現導出がNP困難であることを示し近似アルゴリズムを与えた.玉置は包除原理型指数時間アルゴリズムが有効であるいくつかの計算困難な組合せ問題に対して,論理回路型SATを介する計算量改善が可能であることを示した.[学習論的AL]瀧本は統計的学習問題に関する広範な帰着フレームワークを与えることにより多くの学習問題が複数インスタンス学習問題に帰着できることを示した.また多くのブースティング手法に適用可能なFrank-Wolf法型解釈を与えることにより,収束保証の下での複数の手法を組み合わせを可能とした.[計算論的AL解析] 河村は昇降機などの運行戦略についてオンラインモデル化し,競合比解析を行い従来研究よりも良い戦略や正確な理論的限界を得た.
    2.[圧縮DS] 定兼は様々な交差グラフに対する簡潔表現とそのサイズの最適性の証明を統一的に与える手法を考案した.また半順序集合の簡潔表現も与えた.[計算生物学のDS] 渋谷はゲノムワイド相関解析データにおける統計報公開のための差分プライバシー保護手法について離散フーリエ変換に基づく高速・高精度アルゴリズムの開発に成功した.また結晶の分子構造のグラフ構造の特徴のための数え上げ手法を構築した.
    成果概要に概観したようにほとんどの研究テーマにおいて,数件以上の新成果が得られ,それらは査読付き論文誌・国際学会会議録として採択に至っている.採択された論文誌・国際会議の多くはハイレベルあるいは定評のあるものがほとんどであり,メンバーがそれぞれ自分の強みを生かしながら活躍していると言える.成果の中には,プライバシー保護分野のトップ国際会議IEEE TrustCom(投稿数509、採択数101)でIEEE Outstanding Paper Awardを受賞するなど国際的にも高い評価を受けたもの[Yamamoto+, 2022],メンバーの指導する学生がBest Student Paper Awardを受賞したもの[Kiya+, 2023], その他国内学会等での論文賞・発表賞などを受賞したものなどが含まれており,本研究課題推進は若手研究者育成にも強く関与している.
    さらに,研究代表者の牧野が「離散列挙アルゴリズムとその応用に関する研究」により文部科学大臣表彰科学技術賞を受賞するなど(本研究課題に深く関連する)研究活動が高く評価されている.
    次年度(2023年に研究を行う)以降は,過去3年抑制されてきた対面でのミーティング・セミナー等が開催しやすくなると考えられる.このため積極的なメンバー同士の交流を促し,あるいは機会を設定することにより,アルゴリズム論に関する新たなアイデアの融合・創出の可能性を高める.そのような融合における核となりうる研究テーマ例の一部を以下に挙げる:
    [最適化アルゴリズム] 小野はPSPACEなどNP完全よりもより高い階層に位置する最適化問題に対するアルゴリズム設計に取り組む.[論理的アルゴリズム]玉置は,論理的アルゴリズム設計の観点から, 論理回路の充足可能性問題に対するアルゴリズムとその応用, 量子版の制約充足問題である局所ハミルトニアン問題に対するアルゴリズムの研究に取り組む予定である. [学習論的アルゴリズム]瀧本は,計算学習理論やオンライン意思決定の理論およびその応用に関する研究に取り組む予定である.
    [圧縮データ構造] 定兼は様々なグラフクラスに対する簡潔表現の研究を行う.また,大量の文字列集合を圧縮して保存し,そこから高速に検索するための索引構造についての研究も行う.[計算生物学におけるデータ構造] 渋谷は,生物情報学・医療情報学などで重要とされる問題についてアルゴリズム設計理論の応用を探りながら,より大きなインパクトのある研究をめざし研究を続けていく.

  5. 消費行動分析・効率性分析・サプライチェーン分析を統合した二酸化炭素排出評価

    研究課題/研究課題番号:20H00081  2020年4月 - 2025年3月

    日本学術振興会  科学研究費助成事業 基盤研究(A)  基盤研究(A)

    加河 茂美, 小野 廣隆, 藤井 秀道, 稗貫 峻一, 後藤 美香, 永島 史弥, 馬奈木 俊介, 近藤 康之, 南齋 規介, 小野 廣隆, 藤井 秀道, 稗貫 峻一, 後藤 美香, 永島 史弥, 馬奈木 俊介, 近藤 康之, 南齋 規介

      詳細を見る

    担当区分:研究分担者 

    第一の課題では、自動車の動的離散選択モデルの推定を行い、需要政策が自動車の最終需要に付随するライフサイクルCO2排出量に与える影響を推計し、需要政策が温暖化緩和に果たす役割を定量的に明らかにする。第二の研究課題では、日本の自動車製造に不可欠な金属14部門に着目したサプライチェーンDEAを行い、金属生産の技術効率・サプライチェーン効率の向上が自動車の最終需要に付随するCO2排出量に与える影響を分析する。第三の研究課題では、第一と第二の課題で明らかになる自動車需要政策に伴う最終需要変化と金属部門の効率性向上に伴う投入変化を考慮したサプライチェーンネットワーク分析を行う。
    (1)水素エネルギーシステムのライフサイクル評価に関する研究
    水素エネルギーの利用は、その優れた環境効率とエネルギー効率の点から期待されている。しかしながら、水素エネルギーの社会実装には解決すべき課題が多く残されている。本研究では、化石燃料起源の水素エネルギーとガソリンのライフサイクル比較分析を行った。分析の結果、同じ車両重量に関して、水素自動車のライフサイクル温室効果ガス排出量はガソリン車よりも0.15kg-CO2 eq./km少ないことが分かった。炭素含有量の少ない化石燃料由来の水素は安定したエネルギー供給と経済性の点から、将来のエネルギーシステムに貢献する可能性がある。
    (2)グローバルサプライチェーンの再構築がCO2排出に与える影響に関する研究
    本研究は、4つの産業連関分析手法を統合することで、サプライチェーンの再構築が、カーボンフットプリントに与える影響を分析する新しい解析フレームワークを開発した。さらに、日本の自動車部門を対象としたケーススタディの結果から、当該サプライチェーンの再構築は、自動車のカーボンフットプリントを約 6.5%削減するポテンシャルがあることを明らかにした。この結果は、より低炭素型の構造を持つサプライチェーンの再構築に向けた当該産業のCO2排出削減策・貿易政策の重要性を示唆している。
    (3)グローバルサプライチェーンネットワークにおける媒介中心性に関する研究
    本研究では、産業連関構造抽出分析法と産業連関媒介中心性分析法の理論的な関係を明らかにしただけではなく、グローバルサプライチェーンネットワークにおいて中国の化学製品業、中国の金属製品業の媒介中心性が高いことを示した。この二つの需要な部門に焦点を当てたよりCO2負荷の少ないサプライチェーン構築が求められる。
    自動車のLCA分析において決定的に重要な水素エネルギーシステムに関するインベントリデータの開発ならびにその実証分析を行うことができた。また、サプライチェーンネットワーク解析に関する新手法を開発することもできた。これらの業績は本研究課題を遂行していく上で重要である。またそれらの成果は、International Journal of Hydrogen Energy誌(2021IF=7.139)、Energy Economics誌(2021IF=9.252)、Economic Systems Research誌(2021IF=2.081)というトップジャーナルに掲載された。
    本研究の重要な課題であるグローバルサプライチェーン構造をより深く分析するためのネットワーク解析法の開発を行い、自動車等のグローバルサプライチェーンを研究対象にして実証分析を行っていく予定である。

  6. 準無限スケジューリング問題の分析と応用

    研究課題/研究課題番号:17K19960  2017年6月 - 2021年3月

    日本学術振興会  科学研究費助成事業 挑戦的研究(萌芽)  挑戦的研究(萌芽)

    河村 彰星, 小野 廣隆, 小林 佑輔, 小野 廣隆, 小林 佑輔

      詳細を見る

    担当区分:研究分担者 

    本研究は、多くの者や資源を時間的・空間的にバランスよく配置したり万遍なく行き渡らせたりするための戦略や、それを行うことの困難さについて、理論的保証を念頭に、様々な状況設定に対して分析しようとするものである。本年度の主な論文発表等は以下の通り。
    拡散競争ゲームはネットワーク上を複数の情報等が拡散する様子をゲームとしてモデル化したもので、各プレイヤーの目的は自らの持つ情報をネットワーク構造を介してできるだけ多くのノードに拡散することである。このゲームの挙動は対象とするネットワークの構造に依存し、2人ゲームであってもサイクル構造のためプレイヤーの行動が循環し純粋ナッシュ均衡が存在するとは限らない。本年度の研究ではサイクル構造が限定される強弦グラフであっても純粋ナッシュ均衡が存在しない例が存在すること、より制限された区間グラフなどでは必ず純粋ナッシュ均衡が存在することを示した。
    通常の組合せ最適化問題では解を一つ求めることが目的であるが、実社会においては解を適切に変化させながら維持することが必要とされる場面が数多く存在する。この状況のモデル化として、組合せ最適化問題における解同士の遷移可能性の研究が近年盛んに行われている。本年度の研究では、マッチングの遷移可能性の判定や最短遷移長の計算について、アルゴリズムの設計および計算複雑度の解析を行った。
    なお、当初は年度内に行う計画としていた研究討論会は、渡航制限等の状況により開催困難となったため、次年度に機会を見て行うこととした。

  7. 局所探索型計算のパラメータ化計算量理論

    研究課題/研究課題番号:17H01698  2017年4月 - 2021年3月

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    小野 廣隆, 柳浦 睦憲, 柳浦 睦憲

      詳細を見る

    担当区分:研究代表者 

    配分額:9620000円 ( 直接経費:7400000円 、 間接経費:2220000円 )

    遺伝的アルゴリズム,タブー探索,アニーリングといった計算困難な組合せ最適化問題に対するメタ解法(メタ戦略)は,設計が比較的簡単であり,また実用的には十分な近似精度が得られることが知られている反面,理論的な精度の保障に成功している例は限られている.このためメタ解法の高速化や高精度化に関する研究には職人芸的なものが多いのが現状である.本研究はこれらメタ解法に共通する基本操作である局所探索・局所変形に対し新たにパラメータ化計算の視点を導入し,アルゴリズム設計論・性能分析論を構築する.メタ戦略の高速化・高精度化の非自明性の一つは,局所探索・局所変形の「性能」は近傍系の大きさに依存し,近傍の大きさと探索のための計算量はトレードオフの関係にある.このトレードオフ関係をパラメータ化計算の観点から分析し,局所探索型アルゴリズムのための新たなアルゴリズム設計論・計算論を展開する.
    <BR>
    前年度は有向グラフにおける最適化問題のパラメータ化計算量解明,グラフの擬森化のパラメータ化計算量, 最長増加部分列に対する領域効率のよいアルゴリズム(部分列長がパラメータ)について研究を行い,それぞれの派生問題に対し固定パラメータアルゴリズムの設計可能性や,実際の設計を行ったが,H30年度はこれらを局所探索に展開すべく,グラフ分割問題(ヘドニックゲームを含む),グラフラベリング問題等に対する局所探索に関する計算量に関して考察した.特にグラフ分割(ヘドニックゲーム)のある典型モデルは,次数がある定数以下であったとしてもPLS完全であることがわかるなどの結果が得られた.特にヘドニックゲームなどのエージェント型最適化問題の各エージェントの行動は局所探索アルゴリズムの動作とみなすこともできるため,これらの問題に対する近傍複雑度の研究に次年度以降重点を置くことを考えている.

  8. Combinatorial Optimization

      詳細を見る

    資金種別:競争的資金

  9. 組合せ最適化

      詳細を見る

    資金種別:競争的資金

▼全件表示

 

担当経験のある科目 (本学以外) 2

  1. 微分積分学II

    2017年10月 - 現在

  2. 微分積分学I

    2017年4月 - 現在

 

社会貢献活動 1

  1. 『数学セミナー』での記事掲載

    役割:寄稿

    日本評論社  2020年10月

学術貢献活動 18

  1. 情報処理学会アルゴリズム研究会・主査

    役割:企画立案・運営等

    2024年4月 - 2026年3月

     詳細を見る

    種別:学会・研究会等 

  2. 電子情報通信学会コンピュテーション研究会 副委員長

    役割:企画立案・運営等, パネル司会・セッションチェア等

    2020年5月 - 2022年4月

     詳細を見る

    種別:学会・研究会等 

  3. The 25th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA2024) Program Committee

    役割:企画立案・運営等, 査読

    2024年4月 - 2024年11月

     詳細を見る

    種別:大会・シンポジウム等 

  4. The Twelfth International Symposium on Computing and Networking CANDAR 2024 Program Committee

    役割:企画立案・運営等

    2024年4月 - 2024年11月

     詳細を見る

    種別:大会・シンポジウム等 

  5. JAPAN CONFERENCE ON DISCRETE AND COMPUTATIONAL GEOMETRY, GRAPHS, AND GAMES: JCDCG³

    役割:企画立案・運営等, 査読

    2024年4月 - 2024年9月

     詳細を見る

    種別:大会・シンポジウム等 

  6. 49TH INTERNATIONAL CONFERENCE ON CURRENT TRENDS IN THEORY AND PRACTICE OF COMPUTER SCIENCE SOFSEM 2024, Program Committee

    役割:企画立案・運営等

    2023年2月 - 2024年2月

     詳細を見る

    種別:大会・シンポジウム等 

  7. 電子情報通信学会コンピュテーション研究会・専門委員

    役割:企画立案・運営等

    2022年5月 - 現在

     詳細を見る

    種別:学会・研究会等 

  8. 日本オペレーションズリサーチ学会中部支部 幹事(庶務)

    役割:企画立案・運営等

    2022年3月 - 現在

     詳細を見る

    種別:学会・研究会等 

  9. The Ninth International Symposium on Computing and Networking (CANDAR2021), Program Committee

    役割:企画立案・運営等

    2021年11月

     詳細を見る

    種別:大会・シンポジウム等 

  10. 第33回 RAMP数理最適化シンポジウム・プログラム委員(セッションオーガナイザー)

    役割:企画立案・運営等, パネル司会・セッションチェア等

    日本オペレーションズ・リサーチ学会  2021年 - 2021年11月

     詳細を見る

    種別:大会・シンポジウム等 

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

    役割:企画立案・運営等

    2021年 - 2021年9月

     詳細を見る

    種別:大会・シンポジウム等 

  12. 日本オペレーションズリサーチ学会中部支部 運営委員

    役割:企画立案・運営等

    2020年3月 - 2022年2月

     詳細を見る

    種別:学会・研究会等 

  13. 12th International Conference on Algorithms and Complexity, CIAC2021, program committee

    役割:企画立案・運営等

    2020年 - 2021年5月

     詳細を見る

    種別:大会・シンポジウム等 

  14. The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21), Program committee

    役割:企画立案・運営等

    2020年 - 2021年2月

     詳細を見る

    種別:大会・シンポジウム等 

  15. The 23rd IEEE International Conference on Computational Science and Engineering (CSE 2020) ,Program Committee

    役割:企画立案・運営等

    2020年 - 2021年1月

     詳細を見る

    種別:大会・シンポジウム等 

  16. 18th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA2020, program comittee

    役割:企画立案・運営等

    2020年 - 2020年12月

     詳細を見る

    種別:大会・シンポジウム等 

  17. The 23rd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020, program committee

    役割:企画立案・運営等

    2020年 - 2020年11月

     詳細を見る

    種別:大会・シンポジウム等 

  18. The Eighth International Symposium on Computing and Networking, CANDAR2020, program committee

    役割:企画立案・運営等

    2020年 - 2020年11月

     詳細を見る

    種別:大会・シンポジウム等 

▼全件表示