Horiyama Takashi
| Faculty of Information Science and Technology Computer Science and Information Technology Knowledge Software Science | Professor |
Last Updated :2025/04/12
■Researcher basic information
Researchmap personal page
Home Page URL
Researcher number
- 60314530
J-Global ID
Research Field
Educational Organization
- Bachelor's degree program, School of Engineering
- Master's degree program, Graduate School of Information Science and Technology
- Doctoral (PhD) degree program, Graduate School of Information Science and Technology
■Career
Career
- Sep. 2019 - Present
Hokkaido University, Faculty of Information Science and Technology, Professor, Japan - Apr. 2007 - Aug. 2019
Saitama University, Graduate School of Science and Engineering, Associate Professor, Japan - Jul. 2002 - Mar. 2007
Kyoto University, Graduate School of Informatics, Research Associate, Japan - Apr. 1999 - Jun. 2002
Nara Institute of Science and Technology, Graduate School of Information Science, Research Associate, Japan
Educational Background
- Oct. 1998 - Mar. 1999, Kyoto University, Graduate School of Engineering, Department of Applied Mathematics and Physics, Japan
- Apr. 1995 - Sep. 1998, Kyoto University, Graduate School of Engineering, Department of Information Science, Japan
- Apr. 1991 - Mar. 1995, Kyoto University, Faculty of Engineering, Department of Information Science, Japan
Committee Memberships
- Jun. 2023
情報処理学会 北海道支部, 支部長, Society - Jun. 2019 - May 2021
電子情報通信学会 会誌編集委員会, 編集特別幹事, Society - Jul. 2017 - Mar. 2019
埼玉県情報サービス産業協会, 彩の国さいたまICT コンテスト 審査委員長., Society - Aug. 2013 - Mar. 2019
さいたま市 情報化計画評議会, 評議委員長, Autonomy - May 2016 - Apr. 2018
情報処理学会 アルゴリズム研究専門委員会, 主査, Society - Apr. 2016 - Mar. 2018
電子情報通信学会 基礎・境界ソサイエティ, 運営委員, Society - Jul. 2014 - Jan. 2017
埼玉県情報サービス産業協会, ホームページコンテスト 審査委員長, Society - Jun. 2015 - May 2016
情報処理学会 論文誌ジャーナル/JIP 編集委員会, 基盤グループ 主査, Society - Jun. 2013 - May 2015
情報処理学会 論文誌ジャーナル/JIP 編集委員会, 基盤グループ 副査, Society - Jun. 2009 - May 2015
電子情報通信学会 VLSI設計技術研究専門委員会, 研究専門委員, Society - Jun. 2008 - May 2010
電子情報通信学会, コンピュテーション研究専門委員会 幹事, Society - May 2004 - Apr. 2008
情報処理学会アルゴリズム研究専門委員会, -, Society
■Research activity information
Awards
- Sep. 2018, 電子情報通信学会基礎境界ソサイエティ, 貢献賞
- May 2016, 電子情報通信学会情報・システムソサイエティ, 情報・システムソサイエティ論文編集活動感謝状
- May 2016, 情報処理学会, 感謝状
- Feb. 2011, The 9th EATCS/LA Workshop on Theoretical Computer Science, EATCS/LA Best Presentation Award
Japan - Mar. 2001, 電子情報通信学会 学術奨励賞
Japan - May 2000, 日経BP社 LSI IPデザイン・アワード IP賞
中村一博;朱強;丸岡新治;堀山貴史;木村晋二;渡邉勝正, Japan
Papers
- Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
Shin-ichi Minato, Jun Kawahara, Mutsunori Banbara, Takashi Horiyama, Ichigaku Takigawa, Yutaro Yamaguchi
Discrete Applied Mathematics, 360, 467, 486, Elsevier BV, Jan. 2025
Scientific journal - Explicit description of viral capsid subunit shapes by unfolding dihedrons
Ryuya Toyooka, Seri Nishimoto, Tomoya Tendo, Takashi Horiyama, Tomohiro Tachi, Yasuhiro Matsunaga
Communications Biology, 7, 1, Dec. 2024
Scientific journal, Viral capsid assembly and the design of capsid-based nanocontainers critically depend on understanding the shapes and interfaces of constituent protein subunits. However, a comprehensive framework for characterizing these features is still lacking. Here, we introduce a novel approach based on spherical tiling theory that explicitly describes the 2D shapes and interfaces of subunits in icosahedral capsids. Our method unfolds spherical dihedrons defined by icosahedral symmetry axes, enabling systematic characterization of all possible subunit geometries. Applying this framework to real T = 1 capsid structures reveals distinct interface groups within this single classification, with variations in interaction patterns around 3-fold and 5-fold symmetry axes. We validate our classification through molecular docking simulations, demonstrating its consistency with physical subunit interactions. This analysis suggests different assembly pathways for capsid nucleation. Our general framework is applicable to other triangular numbers, paving the way for broader studies in structural virology and nanomaterial design. - Shortest cover after edit.
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
CoRR, abs/2402.17428, 2024
Scientific journal - Shortest Cover After Edit.
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
CPM, 24, 15, 2024
International conference proceedings - Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs.
Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
IEICE Trans. Inf. Syst., 107, 6, 732, 740, 2024
Scientific journal - 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
AAAI, 20726, 20734, 2024
International conference proceedings - Finding top-k longest palindromes in substrings
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
Theoretical Computer Science, 114183, 114183, Elsevier BV, Sep. 2023
Scientific journal - Internal Longest Palindrome Queries in Optimal Time
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
WALCOM: Algorithms and Computation, 127, 138, Springer Nature Switzerland, Mar. 2023, [Peer-reviewed]
In book - Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs.
Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
CCCG, 191, 196, 2023
International conference proceedings - 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
Scientific journal - Enumerating Empty and Surrounding Polygons
TERUI Shunta, YAMANAKA Katsuhisa, HIRAYAMA Takashi, HORIYAMA Takashi, KURITA Kazuhiro, UNO Takeaki
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, to appear, The Institute of Electronics, Information and Communication Engineers, 2023, [Peer-reviewed]
English, We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2 |ϵ(S) |)-time, where ϵ(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surrounding polygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon. - Geodesic Folding of Regular Tetrahedron
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
Journal for Geometry and Graphics,, 26, 1, 81, 100, Jul. 2022, [Peer-reviewed]
Scientific journal, In this paper, we show geometric properties of a family of polyhedra obtained by folding a regular tetrahedron along triangular grids. Each polyhedron is identified by a pair of nonnegative integers. The polyhedron can be cut along a geodesic strip of triangles to be decomposed and unfolded into one or multiple bands. We show that the number of bands is the greatest common divisor of the two integers. By a proper choice of pairs of numbers, a common triangular band that folds into different multiple polyhedra can be created. We construct the configuration of the polyhedron algebraically and numerically through angular and truss models respectively. We discuss the volumes of the obtained folded states and provide relevant open problems regarding the existence of popped-up state. We also show some geometric connections to other art forms. - Efficient Folding Algorithms for Convex Polyhedra
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, Ryuhei Uehara
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, Jul. 2022, [Peer-reviewed]
English, Scientific journal, We investigate a folding problem that inquires whether a polygon P can be folded, without overlap or gaps, onto a polyhedron Q for given P and Q. An efficient algorithm for this problem when Q is a box was recently developed. We extend this idea to a class of convex polyhedra, which includes the five regular polyhedra, known as Platonic solids. Our algorithms use a common technique, which we call stamping. When we apply this technique, we use two special vertices shared by both P and Q (that is, there exist two vertices of P that are also vertices of Q). All convex polyhedra and their developments have such vertices, except a special class of tetrahedra, the tetramonohedra. We develop two algorithms for the problem as follows. For a given Q, when Q is not a tetramonohedron, we use the first algorithm which solves the folding problem for a certain class of convex polyhedra. On the other hand, if Q is a tetramonohedron, we use the second algorithm to handle this special case. Combining these algorithms, we can conclude that the folding problem can be solved in pseudo-polynomial time when Q is a polyhedron in a certain class of convex polyhedra that includes regular polyhedra. - Efficient Segment Folding is Hard
Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka
Computational Geometry, 104, 101860, Elsevier BV, Jun. 2022, [Peer-reviewed]
Scientific journal - {RePair} Grammars Are the Smallest Grammars for Fibonacci Words.
Takuya Mieno, Shunsuke Inenaga, Takashi Horiyama
CPM, 26, 17, 2022, [Peer-reviewed]
International conference proceedings - Max-Min 3-dispersion Problems
Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 303, 305, 313, Nov. 2021, [Peer-reviewed] - Finding well-optimized special quasirandom structures with decision diagram
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Isao Tanaka
PHYSICAL REVIEW MATERIALS, 5, 11, AMER PHYSICAL SOC, Nov. 2021, [Peer-reviewed]
English, Scientific journal, The advanced data structure of the zero-suppressed binary decision diagram (ZDD) enables us to efficiently enumerate nonequivalent substitutional structures. Not only can the ZDD store a vast number of structures in a compressed manner, but also a set of structures satisfying given constraints can be extracted from the ZDD efficiently. Here, we present a ZDD-based efficient algorithm for exhaustively searching for special quasirandom structures (SQSs) that mimic the perfectly random substitutional structure. We demonstrate that the current approach can extract only a tiny number of SQSs from a ZDD composed of many substitutional structures (>10(12)). As a result, we find SQSs that are optimized better than those proposed in the literature. A series of SQSs should be helpful for estimating the properties of substitutional solid solutions. Furthermore, the present ZDD-based algorithm should be useful for applying the ZDD to the other structure enumeration problems. - Algorithmic enumeration of surrounding polygons
Katsuhisa Yamanaka, David Avis, Takashi Horiyama, Yoshio Okamoto, Ryuhei Uehara, Tanami Yamauchi
Discrete Applied Mathematics, 303, 305, 313, Elsevier BV, Nov. 2021, [Peer-reviewed]
Scientific journal - Longest common subsequence in sublinear space.
Masashi Kiyomi, Takashi Horiyama, Yota Otachi
Information Processing Letters, 168, 106084, 2021, [Peer-reviewed]
Scientific journal - Optimal reconfiguration of optimal ladder lotteries
Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa
Theoretical Computer Science, 859, 57, 69, Elsevier BV, Jan. 2021, [Peer-reviewed]
Scientific journal - Enumeration of nonequivalent substitutional structures using advanced data structure of binary decision diagram
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, Isao Tanaka
JOURNAL OF CHEMICAL PHYSICS, 153, 10, AIP Publishing, Sep. 2020, [Peer-reviewed]
English, Scientific journal, A derivative structure is a nonequivalent substitutional atomic configuration derived from a given primitive cell. The enumeration of derivative structures plays an essential role in searching for the ground states in multicomponent systems. However, it is computationally difficult to enumerate derivative structures if the number of derivative structures of a target system becomes huge. In this study, we introduce a novel compact data structure of the zero-suppressed binary decision diagram (ZDD) for enumerating derivative structures much more efficiently. We show its simple applications to the enumeration of structures derived from the face-centered cubic and hexagonal close-packed lattices in binary, ternary, and quaternary systems. The present ZDD-based procedure should contribute to computational approaches based on derivative structures in physics and materials science. - Rigid foldability is NP-hard.
Hugo Alves Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi
Journal of Computational Geometry, 11, 1, 93, 124, 2020, [Peer-reviewed]
Scientific journal - Efficient Algorithm for Box Folding.
Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara
Journal of Graph Algorithms and Applications, 24, 2, 89, 103, 2020, [Peer-reviewed]
Scientific journal - Efficient Folding Algorithms for Regular Polyhedra.
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, Ryuhei Uehara
Proceedings of the 32nd Canadian Conference on Computational Geometry(CCCG), 121, 127, 2020
International conference proceedings - Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration.
Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato
In Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), 12049, 211, 222, Springer, 2020, [Peer-reviewed]
English, International conference proceedings - Geodesic Folding of Tetrahedron
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
Symmetry: Art and Science, 11th Congress and Exhibition, Nov. 2019 - Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamo, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno
Journal of Graph Algorithms and Applications, 23, 1, 3, 27, Jan. 2019, [Peer-reviewed] - Ecient Segment Folding is Hard.
Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka
Proceedings of the 31st Canadian Conference on Computational Geometry(CCCG), 177, 183, 2019
International conference proceedings - Efficient Algorithm for Box Folding.
Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara
WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings, 277, 288, Springer, 2019, [Peer-reviewed]
International conference proceedings - Max-Min 3-Dispersion Problems
Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
Lecture Notes in Computer Science, 104-A, 9, 291, 300, Springer International Publishing, 2019
In book - Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints
Yu NAKAHATA, Jun KAWAHARA, Takashi HORIYAMA, Shoji KASAHARA
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101.A, 9, 1363, 1374, Institute of Electronics, Information and Communications Engineers (IEICE), 01 Sep. 2018, [Peer-reviewed]
English, Scientific journal - Rep-Cubes: Dissection of a Cube into Nets.
Dawei Xu, Jinfeng Huang, Yuta Nakane, Tomoo Yokoyama, Takashi Horiyama, Ryuhei Uehara
IEICE Transactions, 101-A, 9, 1420, 1430, Sep. 2018, [Peer-reviewed]
Scientific journal - Ladder-Lottery Realization
Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno, Kunihiro Wasa
The proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018), 61, 67, Aug. 2018, [Peer-reviewed], [International Magazine]
English, International conference proceedings - Swapping colored tokens on graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
Theoretical Computer Science, 729, 1, 10, Elsevier B.V., 12 Jun. 2018, [Peer-reviewed]
English, Scientific journal, We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,…,c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for c=3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded. - Exact Algorithms for the Max-Min Dispersion Problem
Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
Proc. of the 12th International Frontiers of Algorithmics Workshop (FAW 2018), Lecture Notes in Computer Science, 10823, 263, 272, Springer International Publishing, Mar. 2018, [Peer-reviewed]
In book - Rigid Foldability is NP-Hard.
Hugo A. Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi
CoRR, abs/1812.01160, 2018
Scientific journal - Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams.
Takashi Horiyama, Masahiro Miyasaka, Riku Sasaki
Proceedings of the 30th Canadian Conference on Computational Geometry(CCCG), 360, 366, 2018
International conference proceedings - Computational Complexity of Robot Arm Simulation Problems.
Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara
Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings, 177, 188, Springer, 2018, [Peer-reviewed]
International conference proceedings - Sankaku-tori: An old Western-japanese game played on a point set
Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
Journal of Information Processing, 25, 708, 715, Information Processing Society of Japan, 01 Aug. 2017, [Peer-reviewed]
English, Scientific journal, We study a combinatorial game named '‘sankaku-tori’' in Japanese, which means '‘triangle-taking’' in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant
for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one
we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy. - Common developments of three incongruent boxes of area 30
Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 64, 1, 12, ELSEVIER SCIENCE BV, Aug. 2017, [Peer-reviewed]
English, Scientific journal, We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that fold into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, and the smallest possible surface area for three different boxes is 46. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge to search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1 x 1 x 7 and 1 x 3 x 3. Moreover, when we fold along diagonal lines of rectangles of size 1 x 2, this area 30 may admit to fold into a box of size root 5 x root 5 x root 5. The results are summarized as follows. There exist 1,080 common developments of two boxes of size 1 x 1 x 7 and 1 x 3 x 3. Among them, there are nine common developments of three boxes of size 1 x 1 x 7, 1 x 3 x 3, and root 5 x root 5 x root 5. Interestingly, one of nine such polygons folds into three different boxes 1 x 1 x 7, 1 x 3 x 3, and root 5 x root 5 x root 5 in four different ways. (C) 2017 Elsevier B.V. All rights reserved. - On the Enumeration of Chequered Tilings in Polygons
Hiroaki Hamanaka, Takashi Horiyama, Ryuhei Uehara
Proc. of Bridges 2017 conference, 423, 426, Jul. 2017, [Peer-reviewed] - Foreword.
Takashi Horiyama
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100-A, 9, 1763, 1763, 2017
Scientific journal - Generating All Patterns of Graph Partitions Within a Disparity Bound
Jun Kawahara, Takashi Horiyama, Keisuke Hotta, Shin-ichi Minato
WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 10167, 119, 131, SPRINGER INTERNATIONAL PUBLISHING AG, 2017, [Peer-reviewed]
English, International conference proceedings, A balanced graph partition on a vertex-weighted graph is a partition of the vertex set such that the partition has k parts and the disparity, which is defined as the ratio of the maximum total weight of parts to the minimum one, is at most r. In this paper, a novel algorithm is proposed that enumerates all the graph partitions with small disparity. Experimental results show that five millions of partitions with small disparity for some graph with more than 100 edges can be enumerated within ten minutes. - Rep-cubes: Unfolding and Dissection of Cubes.
Dawei Xu, Takashi Horiyama, Ryuhei Uehara
Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada, 62, 67, 2017, [Peer-reviewed]
International conference proceedings - Complexity of tiling a polygon with trominoes or bars
Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
Discrete & Computational Geometry, 58, 3, 686, 704, 2017, [Peer-reviewed] - Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno
Proc. of WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, LNCS 10167, 1, 435, 447, SPRINGER INTERNATIONAL PUBLISHING AG, 2017, [Peer-reviewed]
English, International conference proceedings, We consider a puzzle consisting of colored tokens on an nvertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to "sequentially" move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n(3)) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles. - Deciphering Time Scale Hierarchy in Reaction Networks.
Nagahata Y, Maeda S, Teramoto H, Horiyama T, Taketsugu T, Komatsuzaki T
The journal of physical chemistry. B, 120, 8, 1961, 1971, AMER CHEMICAL SOC, Mar. 2016, [Peer-reviewed]
English, Scientific journal, Markovian dynamics on complex reaction networks are one of the most intriguing subjects in a wide range of research fields including chemical reactions, biological physics, and ecology. To represent the global kinetics from one node (corresponding to a basin on an energy landscape) to another requires information on multiple pathways that directly or indirectly connect these two nodes through the entire network. In this paper we present a scheme to extract a hierarchical set of global transition states (TSs) over a discrete time Markov chain derived from first-order rate equations. The TSs can naturally take into account the multiple pathways connecting any pair of nodes. We also propose a new type of disconnectivity graph (DG) to capture the hierarchical organization of different time scales of reactions that can capture changes in the network due to changes in the observation. The crux is the introduction of the minimum conductance cut (MCC) in graph clustering, corresponding to the dividing surface across the network having the "smallest" transition probability between two disjoint subnetworks (superbasins on the energy landscape) in the network. We present a new combinatorial search algorithm for finding this MCC. We apply our method to a reaction network of Claisen rearrangement of allyl vinyl ether that consists of 23 nodes and 66 links (saddles on the energy landscape) connecting them. We compare the kinetic properties of our DG to those of the transition matrix of the rate equations and show that our graph can properly reveal the hierarchical, organization of time scales in a network. - Continuous Folding of Regular Dodecahedra
Takashi Horiyama, Jin-ichi Itoh, Naoki Katoh, Yuki Kobayashi, Chie Nara
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, 9943, 120, 131, SPRINGER INT PUBLISHING AG, 2016, [Peer-reviewed]
English, International conference proceedings, Itoh and Nara [3] discussed with Kobayashi the continuous flattening of all Platonic polyhedra; however, a problem was encountered in the case of the dodecahedron. To complete the study, we explicitly show, in this paper, a continuous folding of a regular dodecahedron following the ideas in [3]. - Common unfolding of regular tetrahedron and Johnson-Zalgaller solid
Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara
Journal of Graph Algorithms and Applications, 20, 1, 101, 104, Brown University, 2016, [Peer-reviewed]
English, Scientific journal, In this paper, we investigate the common unfolding between regular tetrahedra and Johnson-Zalgaller solids. More precisely, we investigate the sets of all edge developments of Johnson-Zalgaller solids that fold into regular tetrahedra. We show that, among 92 Johnson-Zalgaller solids, only J17 (gyroelongated square dipyramid) and J84 (snub disphenoid) have some edge developments that fold into a regular tetrahedron, and the remaining Johnson-Zalgaller solids do not have any such edge development. - Box Pleating is Hard
Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, Ryuhei Uehara
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, 9943, 167, 179, SPRINGER INT PUBLISHING AG, 2016, [Peer-reviewed]
English, International conference proceedings, Flat foldability of general crease patterns was first claimed to be hard for over twenty years. In this paper we prove that deciding flat foldability remains NP-complete even for box pleating, where creases form a subset of a square grid with diagonals. In addition, we provide new terminology to implicitly represent the global layer order of a flat folding, and present a new planar reduction framework for grid-aligned gadgets. - Convex Configurations on Nana-kin-san Puzzle.
Takashi Horiyama, Ryuhei Uehara, Haruo Hosoya
8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, 20:1-20:14, 14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, [Peer-reviewed]
International conference proceedings - 正4 面体と立方体の共通の展開図に関する研究
白川俊博, 堀山貴史, 上原隆平
日 本折紙学会, 折り紙の科学, 4, 1, 45, 54, Mar. 2015, [Peer-reviewed] - Common Developments of Three Incongruent Boxes of Area 30
Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015), 9076, 236, 247, SPRINGER-VERLAG BERLIN, 2015, [Peer-reviewed]
English, International conference proceedings, We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that folds into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, which admits to fold into two boxes of size 1x1x5 and 1x2x3. On the other hand, the smallest possible surface area for three different boxes is 46, which may admit to fold into three boxes of size 1x1x11, 1x2x7, and 1x3x5. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge for search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1x1x7 and 1x3x3. Moreover, when we admit to fold along diagonal lines of rectangles of size 1x2, the area may admit to fold into a box of size root 5x root 5x root 5. That is, the area 30 is the smallest candidate area for folding three different boxes in this manner. We perform two algorithms. The first algorithm is based on ZDDs, zero-suppressed binary decision diagrams, and it computes in 10.2 days on a usual desktop computer. The second algorithm performs exhaustive search, however, straightforward implementation cannot be run even on a supercomputer since it causes memory overflow. Using a hybrid search of DFS and BFS, it completes its computation in 3 months on a supercomputer. As results, we obtain (1) 1,080 common developments of two boxes of size 1x1x7 and 1x3x3, and (2) 9 common developments of three boxes of size 1x1x7, 1x3x3, and root 5 x root 5 x root 5. - Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid.
Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara
WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings, 8973, 294, 305, Springer, 2015, [Peer-reviewed]
English, Common unfolding of a regular tetrahedron and a Johnson-Zalgaller solid is investigated. More precisely, we investigate the sets of all edge unfoldings of Johnson-Zalgaller solids. Among 92 Johnson-Zalgaller solids, some of edge unfolding of J17 and J84 admit to fold into a regular tetrahedron. On the other hand, there are no edge unfolding of the other Johnson-Zalgaller solids that admit to fold into a regular tetrahedron.WALCOM: Algorithms and Computation, 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings - Swapping colored tokens on graphs
Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9214, 619, 628, Springer Verlag, 2015, [Peer-reviewed]
English, International conference proceedings, We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. - Base-object location problems for base-monotone regions
Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
Theoretical Computer Science, 555, 71, 84, ELSEVIER SCIENCE BV, Oct. 2014, [Peer-reviewed]
English, Scientific journal, A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved. - Computational Complexity of Piano-Hinged Dissections
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, Ryuhei Uehara
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E97A, 6, 1206, 1212, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, Jun. 2014, [Peer-reviewed]
English, Scientific journal, We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino. - Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
FUN WITH ALGORITHMS, 8496, 230, 239, SPRINGER-VERLAG BERLIN, 2014, [Peer-reviewed]
English, International conference proceedings, We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general. - Variations on Instant Insanity
ABEL ZACHARY, DEMAINE ERIK D., DEMAINE MARTIN L., HORIYAMA TAKASHI, UEHARA RYUHEI
Lecture Notes in Computer Science, 113, 50, 33, 38, Springer, 17 May 2013
English, We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino. - The Number of Different Unfoldings of Polyhedra.
Takashi Horiyama, Wataru Shoji
Algorithms and Computation - 24th International Symposium(ISAAC), 623, 633, Springer, 2013
International conference proceedings - Enumeration of region partitioning for evacuation planning based on ZDD
Atsushi Takizawa, Yasufumi Takechi, Akio Ohta, Naoki Katoh, Takeru Inoue, Takashi Horiyama, Jun Kawahara, Shin-Ichi Minato
Proc. of the 11th International Symposium on Operations Research and its Applications in engineering, technology and management, 64, 71, Institution of Engineering and Technology, 2013, [Peer-reviewed]
English, International conference proceedings, Japanese cities always have risks of large-scale earthquakes. Thus, it is very important to establish crisis management systems against large-scale disasters such as big earthquakes, and tsunamis to secure evacuation centers for evacuees. In this respect, it is extremely important to provide sufficient evacuation centers and to appropriately partition the whole region into small areas, such that a unique evacuation center is located in each area and the people living in the area can easily evacuate to the center. However, it is hard to find an optimal region partitioning, due to the uncertainty, such as a fire or collapsed buildings. In this research, we propose a method to enumerate all partitioning patterns using Zero-suppressed Binary Decision Diagram (ZDD) that satisfy several conditions. We apply the proposed method to Kamigyo Ward of Kyoto City, Japan. © 2013 IET. - Base location problems for base-monotone regions
Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, 7748, 53, 64, Springer, 2013, [Peer-reviewed]
English, The problem of decomposing a pixel grid into base-monotoneregions was first studied in the context of image segmentation. It is known that for a given n × n pixel grid and baselines, one can compute in O(n^3) time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. To complement this fact, we first show the NP-hardness of the problem of optimally locating k baselines in a given pixel grid. Next we present an O(n^3)-time 2-approximation algorithm for this problem. We also study some polynomial-time solvable cases, and variants of the problem.WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings - Automatic Multi-Stage Clock Gating Optimization Using ILP Formulation
Xin Man, Takashi Horiyama, Shinji Kimura
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E95A, 8, 1347, 1358, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, Aug. 2012, [Peer-reviewed]
English, Scientific journal, Clock gating is supported by commercial tools as a power optimization feature based on the guard signal described in HDL (structural method). However, the identification of control signals for gated registers is hard and designer-intensive work. Besides, since the clock gating cells also consume power, it is imperative to minimize the number of inserted clock gating cells and their switching activities for power optimization. In this paper, we propose an automatic multi-stage clock gating algorithm with ILP (Integer Linear Programming) formulation, including clock gating control candidate extraction, constraints construction and optimum control signal selection. By multi-stage clock gating, unnecessary clock pulses to clock gating cells can be avoided by other clock gating cells, so that the switching activity of clock gating cells can be reduced. We find that any multi-stage control signals are also single-stage control signals, and any combination of signals can be selected from single-stage candidates. The proposed method can be applied to 3 or more cascaded stages. The multi-stage clock gating optimization problem is formulated as constraints in LP format for the selection of cascaded clock-gating order of multi-stage candidate combinations, and a commercial ILP solver (IBM CPLEX) is applied to obtain the control signals for each register with minimum switching activity. Those signals are used to generate a gate level description with guarded registers from original design, and a commercial synthesis and layout tools are applied to obtain the circuit with multi-stage clock gating. For a set of benchmark circuits and a Low Density Parity Check (LDPC) Decoder (6.6k gates, 212 F.F.s), the proposed method is applied and actual power consumption is estimated using Synopsys NanoSim after layout. On average, 31% actual power reduction has been obtained compared with original designs with structural clock gating, and more than 10% improvement has been achieved for some circuits compared with single-stage optimization method. CPU time for optimum multi-stage control selection is several seconds for up to 25k variables in LP format. By applying the proposed clock gating, area can also be reduced since the multiplexors controlling register inputs are eliminated. - Packing Trominoes is NP-Complete, #P-Complete and ASP-Complete.
Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
Proceedings of the 24th Canadian Conference on Computational Geometry(CCCG), 211, 216, 2012
International conference proceedings - Power Optimization of Sequential Circuits Using Switching Activity Based Clock Gating
Xin Man, Takashi Horiyama, Shinji Kimura
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E93A, 12, 2472, 2480, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, Dec. 2010, [Peer-reviewed]
English, Scientific journal, Clock gating is the insertion of control signal for registers to switch off unnecessary clock signals selectively without violating the functional correctness of the original design so as to reduce the dynamic power consumption Commercial EDA tools usually have a mechanism to generate clock gating logic based on the structural method where the con trol signals specified by designers are used and the effectiveness of the clock gating depends on the specified control signals In the research we focus on the automatic clock gating logic generation and propose a method based on the candidate extraction and control signal selection We formalize the control signal selection using linear formulae and devise an optimization method based on BDD The method is effective for circuits with a lot of shared candidates by different registers The method is applied to counter circuits to check the co relation with power simulation results and a set of benchmark circuits 19 1-71 9% power reduction has been found on counter circuitsafter layout and 2 3-18 0% cost reduction on benchmark circuits - Generation of Polyiamonds for p6 Tiling by the Reverse Search.
Takashi Horiyama, Shogo Yamane
Computational Geometry, Graphs and Applications - 9th International Conference(CGGA), 96, 107, Springer, 2010
International conference proceedings - Enumeration of Polyominoes for p4 Tiling.
Takashi Horiyama, Masato Samejima
Proceedings of the 21st Annual Canadian Conference on Computational Geometry(CCCG), 29, 32, 2009
International conference proceedings - Fine-Grained Power Gating Based on the Controlling Value of Logic Elements
Lei Chen, Takashi Horiyama, Yuichi Nakamura, Shinji Kimura
IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E91-A, 12, 3531, 3538, Dec. 2008, [Peer-reviewed] - Enumeration of Tsume-Shogi diagrams by the reverse method
Takashi Horiyama, Hiro Ito, Kazuo Iwama, Jun Kawahara
INTERNATIONAL CONFERENCE ON INFORMATICS EDUCATION AND RESEARCH FOR KNOWLEDGE-CIRCULATING SOCIETY, PROCEEDINGS, 193, +, IEEE COMPUTER SOC, 2008, [Peer-reviewed]
English, International conference proceedings, With the advances of modern computer technologies and elaborated algorithm design methodologies, it becomes important to enumerate all feasible solutions for given constraints. In this paper, we propose algorithms for enumerating Tsume-Shogi diagrams (i.e., Shogi. mating problems) by the reverse method. Conventional algorithms always take the principle 'generate candidate diagrams and sieve them by Tsume-Shogi solvers,' which tends to require lengthy execution time. In our approach, the reverse method enables us to enumerate all diagrams without using Tsume-Shogi solvers. We can sieve the candidates easily and quickly, since the), are generated in the ascending order according to the number of necessary moves for mating the defender's king. We have implemented the proposed algorithms, and enumerated all diagrams with several restrictions (e.g., those with only four knights). From this result, we prove many results for knight diagrams, e.g., i) the maximum number of moves is 11, ii) it is 13 for additional mate free, iii) it is 7 if at least one piece is in hand of the attacker, and iv) the maximum pieces in hand of the attacker is two. - Bit-Length Optimization Method for High-Level Synthesis Based on Non-Linear Programming Technique
Nobuhiro Doi, Takashi Horiyama, Masaki Nakanishi, Shinji Kimura
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A, 12, 3427, 3434, The Institute of Electronics, Information and Communication Engineers, Dec. 2006, [Peer-reviewed]
English, Scientific journal, High-level synthesis is a novel method to generate a RT-level hardware description automatically from a high-level language such as C, and is used at recent digital circuit design. Floating-point to fixed-point conversion with bit-length optimization is one of the key issues for the area and speed optimization in high-level synthesis. However, the conversion task is a rather tedious work for designers. This paper introduces automatic bit-length optimization method on floating-point to fixed-point conversion for high-level synthesis. The method estimates computational errors statistically, and formalizes an optimization problem as a non-linear problem. The application of NLP technique improves the balancing between computational accuracy and total hardware cost. Various constraints such as unit sharing, maximum bit-length of function units can be modeled easily, too. Experimental result shows that our method is fast compared with typical one, and reduces the hardware area. - Finite-state online algorithms and their automated competitive analysis
Takashi Horiyama, Kazuo Iwama, Jun Kawahara
In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), 4288, 71, 80, Dec. 2006, [Peer-reviewed]
English, International conference proceedings - How to collect balls moving in the Euclidean plane
Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Hirotaka Ono, Toshinori Sakuma, Masafumi Yamashita
DISCRETE APPLIED MATHEMATICS, 154, 16, 2247, 2262, ELSEVIER SCIENCE BV, Nov. 2006, [Peer-reviewed]
English, Scientific journal, In this paper, we study how to collect n balls moving with a fixed constant velocity in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls; (ii) maximizing the number of the balls collected by k robots; (iii) minimizing the number of the robots to collect all n balls. The situations considered in this paper contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability-intractability frontier in the ball collecting problems in the Euclidean plane. (c) 2006 Published by Elsevier B.V. - Density condensation of Boolean formulas
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama
Discrete Applied Mathematics, 154, 16, 2263, 2270, 01 Nov. 2006, [Peer-reviewed]
English, Scientific journal, The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is "easier" than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2n, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. © 2006 Elsevier B.V. All rights reserved. - An Optimization Method in Floating-point to Fixed-point Conversion using Positive and Negative Error Analysis and Sharing of Operations
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura
Proc. of the 12th Workshop on Synthesis And System Integration of Mixed Information technologies(SASIMI 2004), 466, 471, Oct. 2004, [Peer-reviewed]
English, International conference proceedings - Reasoning with ordered binary decision diagrams
T Horiyama, T Ibaraki
DISCRETE APPLIED MATHEMATICS, 142, 1-3, 151, 163, ELSEVIER SCIENCE BV, Aug. 2004, [Peer-reviewed]
English, Scientific journal, We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram, for two cases of general and Horn knowledge-bases. Our main results say that both finding a model of a knowledge-base and deducing from a knowledge-base can be done in linear time for a general knowledge-base, but that abduction is NP-complete even for a Horn knowledge-base. Then, we consider abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases are also discussed. (C) 2004 Elsevier B.V. All rights reserved. - How to collect balls moving in the euclidean plane
Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Hirotaka Ono, Toshinori Sakuma, Masafumi Yamashita
Electronic Notes in Theoretical Computer Science, 91, 229, 245, 16 Feb. 2004, [Peer-reviewed]
English, International conference proceedings, In this paper, we study how to collect n balls moving with constant velocities in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-Target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls, (ii) maximizing the number of the balls collected by k robots, and (iii) minimizing the number of the robots to collect all n balls. The situations considered here contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability- intractability frontier in the ball collecting problems in the Euclidean plane. © 2004 Elsevier B.V. All rights reserved. - Density condensation of Boolean formulas
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama
Proc. of the 6th International Conference on Theory and Application of Satisfiability Testing, Lecture Notes in Computer Science, 2919, 69, 77, SPRINGER-VERLAG BERLIN, 2004, [Peer-reviewed]
English, Scientific journal, The following problem is considered: Given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is "easier" than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments) / 2(n), where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem axe presented: One is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. This is a preliminary report of the on-going research. - Minimization of Fractional Wordlength on Fixed-Point Conversion for High-Level Synthesis
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura
In. Proc. of Asia and South Pacific Design Automation Conference 2004 (ASP-DAC 2004), 80, 85, Jan. 2004, [Peer-reviewed]
English, International conference proceedings - Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, K. Watanabe
IEICE Trans. Fundamentals, E86-A, 12, 3184, 3191, The Institute of Electronics, Information and Communication Engineers, Dec. 2003, [Peer-reviewed]
English, Scientific journal, In the hardware synthesis from a high-level language such as C, the bit length of variables is one of the key issues for the area and speed optimization. Usually, designers are required to optimize the bit-length of each variable manually using the time-consuming simulation on huge-data. In this paper, we propose an optimization method of the fractional bit length in the conversion from floating-point variables to fixed-point variables. The method is based on error propagation and the backward propagation of the accuracy limitation. The method is fully analytical and fast compared to simulation based methods. - Finding essential attributes from binary data
E Boros, T Horiyama, T Ibaraki, K Makino, M Yagiura
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 39, 3, 223, 257, SPRINGER, Nov. 2003, [Peer-reviewed]
English, Scientific journal, We consider data sets that consist of n-dimensional binary vectors representing positive and negative examples for some ( possibly unknown) phenomenon. A subset S of the attributes ( or variables) of such a data set is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we study the problem of finding small support sets, a frequently arising task in various fields, including knowledge discovery, data mining, learning theory, logical analysis of data, etc. We study the distribution of support sets in randomly generated data, and discuss why finding small support sets is important. We propose several measures of separation ( real valued set functions over the subsets of attributes), formulate optimization models for finding the smallest subsets maximizing these measures, and devise efficient heuristic algorithms to solve these ( typically NP-hard) optimization problems. We prove that several of the proposed heuristics have a guaranteed constant approximation ratio, and we report on computational experience comparing these heuristics with some others from the literature both on randomly generated and on real world data sets. - Bit Length Optimization of Fractional Parts on Floating to Fixed Point Conversion for High-Level Synthesis
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, K. Watanabe
Proc. of 12th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI2003), 129, 136, Apr. 2003, [Peer-reviewed]
English, International conference proceedings - Translation among CNFs, characteristic models and ordered binary decision diagrams
Takashi Horiyama, Toshihide Ibaraki
Information Processing Letters, 85, 4, 191, 198, ELSEVIER SCIENCE BV, Feb. 2003, [Peer-reviewed]
English, Scientific journal, We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their Horn CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results hold on any class of functions having a basis of polynomial size. (C) 2002 Elsevier Science B.V. All rights reserved. - An On-Chip High Speed Serial Communication Method Based on Independent Ring Oscillators
S. Kimura, T. Hayakawa, T. Horiyama, M. Nakanishi, K. Watanabe
Proc. of International Solid-State Circuits Conference (ISSCC2003), 390, 391, Feb. 2003, [Peer-reviewed]
English, International conference proceedings - Look up table compaction based on folding of logic functions
S Kimura, A Ishii, T Horiyama, M Nakanishi, H Kajihara, K Watanabe
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E85A, 12, 2701, 2707, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, Dec. 2002, [Peer-reviewed]
English, Scientific journal, The paper describes the folding method of logic functions to reduce the size of memories to keep the functions. The folding is based on the relation of fractions of logic functions. If the logic function includes 2 or 3 same parts, then only one part should be kept and other parts can be omitted. We show that the logic function of I-bit addition can be reduced to half size using the bit-wise NOT relation and the bit-wise OR relation. The paper also introduces 3-1 LUT's with the folding mechanism. A full adder can be implemented using only one 3-1 LUT with the folding. Multi-bit AND and OR operations can be mapped to our LUT's not using the extra cascading circuit but using the carry circuit for addition. We have also tested the mapping capability of 4 input functions to our 3-1 LUT's with folding and carry propagation mechanisms. We have shown the reduction of the area consumption when using our LUT's compared to the case using 4-1 LUT's on several benchmark circuits. - Folding of Logic Functions and Its Application to Look Up Table Compaction
S. Kimura, T. Horiyama, M. Nakanishi, H. Kajihara
Proc. of International Conference on Computer Aided Design (ICCAD2002), 694, 698, Nov. 2002, [Peer-reviewed]
English, International conference proceedings - Ordered binary decision diagrams as knowledge-bases
Takashi Horiyama, Toshihide Ibaraki
Artificial Intelligence, 136, 2, 189, 213, ELSEVIER SCIENCE BV, Apr. 2002, [Peer-reviewed]
English, Scientific journal, We consider the use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases, and show that, from the view point of space requirement, the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations. We then present polynomial time algorithms for the two problems of testing whether a given OBDD represents a unate Boolean function, and of testing whether it represents a Horn function. (C) 2002 Published by Elsevier Science B.V. - Translation among CNFs, characteristic models and ordered binary decision diagrams
Takashi Horiyama, Toshihide Ibaraki
Proc. of the 12th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 2223, 231, 243, SPRINGER-VERLAG BERLIN, Dec. 2001, [Peer-reviewed]
English, Scientific journal, We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results holds on any class of functions having a basis B with \B\ = d. - Speech Recognition Chip for Monosyllables
Kazuhiro Nakamura, Qiang Zhu, Shinji Maruoka, Takashi Horiyama, Shinji Kimura, Katsumasa Watanabe
Proc. of the 6th Asia and South Pacific Design Automation Conference, 396, 399, Jan. 2001, [Peer-reviewed] - A Real-time 64-Monosyllable Recognition LSI with Learning Mechanism
Kazuhiro Nakamura, Qiang Zhu, Shinji Maruoka, Takashi Horiyama, Shinji Kimura, Katsumasa Watanabe
Proc. of the 6th Asia and South Pacific Design Automation Conference, 31, 32, Jan. 2001, [Peer-reviewed] - Reasoning with ordered binary decision diagrams
Takashi Horiyama, Toshihide Ibaraki
Proc. of the 11th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 1969, 120, 131, SPRINGER-VERLAG BERLIN, Dec. 2000, [Peer-reviewed]
English, Scientific journal, We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram (OBDD), for two special cases of general and Horn knowledge-bases. Our main results say that both finding a, model of a knowledge-base and deducing from a knowledge-base. can be done in linear time for general case, but that abduction is NP-complete even if the knowledge-base is restricted to be Horn. Then, we consider the abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases axe also discussed. - New Graph Calculi for Planar Non-3-Colorable Graphs,
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama, Suguru Tamaki
IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E91-A, 9, 2301, 2307, Sep. 2000, [Peer-reviewed] - Finding Essential Attributes in Binary Data.
Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Mutsunori Yagiura
Proc. of the 2nd International Conference on Intelligent Data Engineering and Automated Learning, Lecture Notes in Computer Science, 1983, 133, 138, Springer, 2000, [Peer-reviewed]
International conference proceedings - Ordered binary decision diagrams as knowledge-bases
Takashi Horiyama, Toshihide Ibaraki
Proc. of the 10th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 1741, 83, 92, SPRINGER-VERLAG BERLIN, 2000, [Peer-reviewed]
English, Scientific journal, We propose to make use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases. We show that the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations in the sense of space requirement. We then consider two recognition problems of OBDDs, and present polynomial time algorithms for testing whether a given OBDD represents a unate Boolean function, and whether it represents a Horn function. - A High-Speed Reduced-Size Adder Under Left-to-Right Input Arrival.
Naofumi Takagi, Takashi Horiyama
IEEE Transactions on Computers, 48, 1, 76, 80, 1999, [Peer-reviewed]
Scientific journal - Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
Takashi Horiyama, Shuzo Yajima
IEICE Trans. Inf. & Syst, E81-D, 8, 793, 800, Aug. 1998, [Peer-reviewed] - Exponential Lower Bounds on the Size of OBDDs Representing Integer Divistion.
Takashi Horiyama, Shuzo Yajima
Proc. of the 8th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 1350, 163, 172, Springer, 1997, [Peer-reviewed]
International conference proceedings
Other Activities and Achievements
- Enumeration of Non-isomorphic Unordered Trees with Degree Sequence Constraints
Shuhei Denzumi, Takashi Horiyama, Kazuhiro Kurita, Atsuki Nagao, Kazuhisa Seto, Kunihiro Wasa, 情報処理学 会, アルゴリズム研究会, 192, 11, 1, 6, May 2023 - ZDD を用いた最適円 筒あみだくじの列挙
岩崎善泰, 堀山貴史, 松井泰子, 野崎雄太, 脊戸和寿, 山中克久, 情報処理学会, アルゴリズム研究会, 192, 3, 1, 8, Mar. 2023 - あみだくじと菱形タイリングの列挙
堀山貴史, 科学研究費補助金学術 変革領域(B) 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチ の融合, 第34 回セミナー, Jan. 2023, [Invited] - 自己同型写像の断片を用いた代表元の反復抽出によ る同型性の除去
高橋孔平, 脊戸和寿, 堀山貴史, 電子情報通信学会技術研究報告, 122, 294, 51, 58, Dec. 2022 - 最小重み Laman グラフの総交点数と厚みの下界の改良
河上悠輝, 高橋駿, 脊戸和寿, 堀山貴史, 小林祐貴, 東川雄哉, 加藤直樹, 第35 回回路とシステムワークショッ プ, 191, 196, Aug. 2022 - 文字列中の異なる閉文字列の数え上げと 最大個数について
高橋駿, 脊戸和寿, 堀山貴史, 三重野琢也, 夏のLAシンポジウム, Jul. 2022 - 区間最長回文クエリに対する時間最適 アルゴリズム
三谷和暉, 脊戸和寿, 堀山貴史, 三重野琢也, 夏のLAシンポジウム, 2.1, 2.8, Jul. 2022 - 最小重み Laman グラフの総交点数と厚みの下界の改良
河上悠輝, 高橋駿, 脊戸和寿, 堀山貴史, 小林祐貴, 東川雄哉, 加藤直樹, 夏のLAシンポジウム, 4.1, 4.7, Jul. 2022 - 複数の多面体の共通の展開図について
堀山貴史, 科学研究費補助金学術 変革領域(A) 社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化, AFSA コロキウム, Jul. 2022, [Invited] - 正四面体の測地線折り
西本清里, 堀山貴史, 舘知宏, 第32 回折り紙の科学・数学・ 教育研究集会, Jun. 2022 - Solving Rep-tile by Computers
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda, 14th Gathering 4 Gardner Conference, Apr. 2022 - レプ・タイルの定式化を用いた各種ソルバの性能比較
番原睦則, 橋本健二, 堀山貴史, 湊真一, 中村駆, 西野正彬, 酒井正彦, 上原隆平, 宇野, 裕之, 安田宜仁, 第16 回組合せ ゲーム・パズル研究集会, Mar. 2022 - ZDD の区間メモ化探索 技法によるコスト制約組合せ問題の高速な解列挙
湊真一, 番原睦則, 堀山貴史, 川原純, 瀧川一学, 山口勇太郎, 情報処理学会, アルゴリズム研究会, 1, 8, Mar. 2022 - 45度系格子パターンにおける局 所平坦折り可能な展開図の数え上げとZDDによる列挙
榎本優大, 河上悠輝, 脊戸和寿, 堀山貴史, 三谷純, 冬のLAシンポジウム, 6.1, 6.12, Feb. 2022 - フィボナッチ文字列の最小文法は RePair 文法
三重野琢也, 稲永俊介, 堀山貴史, 冬のLAシンポジウム, 20.1, 20.3, Feb. 2022 - あみだくじと菱形タイリングの列挙
堀山貴史, 人工知能学会, 第119 回 人工知能基本問題研究会, 1, Jan. 2022, [Invited] - Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions.
Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi 0005, CoRR, abs/2201.08118, Jan. 2022 - ポリオミノ と格子凸多角形による多層タイル張り
千田皐汰, Erik Demaine, Martin Demaine, David Eppstein, Adam Hesterberg, 堀山貴史, John Iacono, 伊藤大雄, Stefan Langerman, 上原隆平, 宇野裕之, 電子情報通信学会技術研究報告, 121, 218, 11, 18, Oct. 2021 - Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions.
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda, CoRR, abs/2110.05184, Oct. 2021 - ZDD による45 度系格子パターンにおける局 所平坦折り可能な展開図の列挙
榎本優大, 脊戸和寿, 堀山貴史, 三谷純, 第29 回折り紙の科学・数学・教育研究集会, Jun. 2021 - 動的計画法に基づくSimple Polygonization 列挙アルゴリズムの実験的評価
中畑裕, 堀山貴史, 湊真一, 山中克久, 情報処理学会, アルゴリズム研究会, 1, 8, Mar. 2021 - コスト制約つき組合せ問題に対するZDDを用いた高速な解列挙手法
湊真一, 番原睦則, 堀山貴史, 川原純, 瀧川一学, 山口勇太郎, 電子情報通信学会技術研究報告, 120, 276, 8, 15, Dec. 2020 - 覆面算を列挙するオートマトンの効率的な構築手法
渡部航也, ヘンリアンディプタラマ, 吉仲亮, 堀山貴史, 篠原歩, 電子情報通信学会技術研究報告,, 120, 276, 16, 23, Dec. 2020 - 正多面体の折り判定問題の多項式時間解法
上原隆平, 門口あきら, 鎌田斗南, 堀山貴史, 第29 回折り紙の科学・数学・教育研究集会, Dec. 2020 - Sorting by Five Prefix Reversals
Tetsuya Araki, Takashi Horiyama, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, 情報処理学会, アルゴリズム研究会, 1, 7, Sep. 2020 - Polyhedral Forms from Folding Geodesic Strips
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi, Virtual Technical Meeting of the Society of Engineering Science, Sep. 2020 - Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization.
Yu Nakahata, Takashi Horiyama, Shin-ichi Minato, Katsuhisa Yamanaka, CoRR, abs/2001.08899, Jan. 2020
English, Technical report - Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration.
Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato, CoRR, abs/1911.07465, Nov. 2019
English, Technical report - Enumeration with Isomorphism Elimination
Takashi Horiyama, The 3rd International Workshop on Enumeration Problems & Applications, Oct. 2019, [Invited] - Decomposing a Graph into Unigraphs.
Takashi Horiyama, Jun Kawahara, Shin-ichi Minato, Yu Nakahata, CoRR, abs/1904.09438, 2019
English, Technical report - The Complexity of Ladder-Lottery Realization Problem (回路とシステム)
YAMANAKA KATSUHISA, HORIYAMA TAKASHI, UNO TAKEAKI, WASA KUNIHIRO, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 118, 295, 1, 6, 12 Nov. 2018
電子情報通信学会, English - The Complexity of Ladder-Lottery Realization Problem (システム数理と応用)
YAMANAKA KATSUHISA, HORIYAMA TAKASHI, UNO TAKEAKI, WASA KUNIHIRO, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 118, 296, 1, 6, 12 Nov. 2018
電子情報通信学会, English - Enumerating Acyclic Contractions of a Directed Acyclic Graph Using Frontier-Based Search
NAKAHATA Yu, SUZUKI Hirofumi, ISHIHATA Masakazu, HORIYAMA Takashi, Proceedings of the Annual Conference of JSAI, JSAI2018, 4K1OS16a03, 4K1OS16a03, 2018
有向非巡回グラフ（DAG）は計算機科学における基本的な構造である． 応用において，DAGをより小さなDAGに縮約する問題は，命令セット拡張問題等のために重要である． 本研究では，DAGが与えられたとき，いくつかの辺を選んで縮約した結果がDAGとなるような辺の選び方をすべて列挙するアルゴリズムを提案する． 提案手法はフロンティア法に基づき，所望の辺部分集合の族を表現するデータ構造ZDDを構築するアルゴリズムである．, The Japanese Society for Artificial Intelligence, Japanese - Enumeration and Random Sampling of Nonisomorphic Two-Terminal Series-Parallel Graphs
伝住周平, 堀山貴史, 栗田和宏, 中畑裕, 鈴木浩史, 和佐州洋, 山崎一明, 電子情報通信学会技術研究報告, 118, 216(COMP2018 9-20)(Web), 2018 - On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
Horiyama Takashi, Ito Takehiro, Ono Hirotaka, Otachi Yota, Uehara Ryuhei, Uno Takeaki, 数理解析研究所講究録, 1799, 123, 129, Jun. 2012
京都大学数理解析研究所, English - Minimum Enclosing Rectangle with Fixed Aspect Ratio (New Trends in Algorithms and Theory of Computation)
小林 有, 堀山 貴史, 数理解析研究所講究録, 1799, 65, 66, Jun. 2012
京都大学数理解析研究所, Japanese - Edge-Developments of Platonic Solids Never Overlap : Extended Abstrsct (Mathematical Foundations and Applications of Computer Science and Algorithms)
Horiyama Takashi, Shoji Wataru, RIMS Kokyuroku, 1744, 159, 160, Jun. 2011
Kyoto University, English - Secure Vickrey Auction Based on Secret Sharing
SUGIMOTO Takuma, HORIYAMA Takashi, IEICE technical report, 110, 232, 19, 25, 08 Oct. 2010
Vickrey auction, in which the highest bidder wins at the second highest price, is a well-known incentive compatible auction. For achieving the privacy of bidders, we can run the auction without revealing the bidding prices to bidders, while it allows the auctioneer to cheat the second highest bidding price. In this paper, we propose making use of the techniques of secret sharing, and design an information-theoretically secure protocol that prohibits auctioneers from cheating the bidders, and that does not leak any additional information against the set of size t1-D-5 最長路問題と最大経路差問題 : その解法とJR大都市近郊区間大回りへの応用(離散・組合せ最適化(2))
堀山 貴史, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2009, 80, 81, 09 Sep. 2009
公益社団法人日本オペレーションズ・リサーチ学会, JapaneseThe Longest Path Problem and Its Application to the Path Selection in JR Urban Areas
HORIYAMA Takashi, HIGUCHI Kosuke, IEICE technical report, 109, 108, 17, 21, 22 Jun. 2009
The longest path problem is, given an undirected graph with non-negative integer weights for the edges, to find the simple path of the largest length. Although the shortest path problem has brilliant algorithms in the literature, the longest path has no efficient algorithms. In this paper, we treat the longest path problem, the s-t longest path problem, and the all pairs longest path problem. For these problems, we propose two types of algorithms based on the exhaustive search and the 0-1 integer programming. We also implement and evaluate the algorithms by the benchmark instances of the path selection in JR Urban areas., The Institute of Electronics, Information and Communication Engineers, JapaneseEnumerating Polyominoes of p4 Tiling by the Reverse Search (Theoretical Computer Science and Its Applications)
HORIYAMA Takashi, SAMEJIMA Masato, RIMS Kokyuroku, 1649, 55, 57, May 2009
Kyoto University, EnglishEnumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search
T. Horiyama, M. Samejima, Proc. of the 2nd Asian Association for Algorithms and Computation Annual Meeting, (to appear), 2009Enumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search
T. Horiyama, M. Samejima, Proc. of the 2nd Asian Association for Algorithms and Computation Annual Meeting, (to appear), 2009Fine-Grained Power Gating Based on the Controlling Value of Logic Gates
CHEN Lei, HORIYAMA Takashi, NAKAMURA Yuichi, KIMURA Shinji, IEICE technical report, 108, 23, 19, 24, 09 May 2008
Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method, sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay., The Institute of Electronics, Information and Communication Engineers, EnglishFine-Grained Power Gating Based on the Controlling Value of Logic Gates
CHEN Lei, HORIYAMA Takashi, NAKAMURA Yuichi, KIMURA Shinji, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2008, 38, 55, 60, 01 May 2008
Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method, sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay., Information Processing Society of Japan (IPSJ), EnglishDensity Condensation of Boolean Formulas Based on Covering Codes
T. Horiyama, A. Sato, Proc. of the 1st Asian Association for Algorithms and Computation Annual Meeting, 1, 28, 2008The Complexity of the Hajos Calculus on Planar Graphs
HANATANI Yoichi, HORIYAMA Takashi, IWAMA Kazuo, TAMAKI Suguru, IEICE technical report, 107, 219, 43, 50, 13 Sep. 2007
The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calculus is polynomially bounded., The Institute of Electronics, Information and Communication Engineers, EnglishTruthful Auctions with Limited Range of Bids
T. Horiyama, K. Iwama, D. Sumita, Proc. of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 5, 53, 61, 2007Maximum Power Consumption Ratio on Two-Level Circuits(New Trends in Theory of Computation and Algorithm)
ANNO Takafumi, HORIYAMA Takashi, IWAMA Kazuo, RIMS Kokyuroku, 1489, 188, 194, May 2006
Kyoto University, JapaneseBit-length Optimization Method for High-level Synthesis based on Non-linear Programming and Searching Integer Solutions
DOI Nobuhiro, HORIYAMA Takashi, NAKANISHI Masaki, KIMURA Shinji, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2005, 27, 133, 138, 18 Mar. 2005
This paper presents bit-length optimization technique for high-level synthesis based on non-linear programming and searching integer solutions. The results of the bit-length optimization based on non-linear programming are real values, and these values are converted to integer with round-up for hardware implementation. In this paper, we show a method to search integer solutions under the constraints of the real solution. The experimental results shows the advantage of searching based method., Information Processing Society of Japan (IPSJ), JapaneseBit-length Optimization Method for High-level Synthesis based on Non-linear Programming and Searching Integer Solutions
DOI Nobuhiro, HORIYAMA Takashi, NAKANISHI Masaki, KIMURA Shinji, IEICE technical report. Computer systems, 104, 738, 43, 48, 11 Mar. 2005
This paper presents bit-length optimization technique for high-level synthesis based on non-linear programming and searching integer solutions. The results of the bit-length optimization based on non-linear programming are real values, and these values are converted to integer with round-up for hardware implementation. In this paper, we show a method to search integer solutions under the constraints of the real solution. The experimental results shows the advantage of searching based method., The Institute of Electronics, Information and Communication Engineers, JapaneseProgram Analysis Based on Abstruct Interpretation and Its Application for Datapath Optimization
DOI Nobuhiro, HORIYAMA Takashi, NAKANISHI Masaki, KIMURA Shinji, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2004, 56, 41, 46, 28 May 2004
Various optimization techniques such as bit-length optimization are required for hardware generation from C programs. The value range analysis and dataflow analysis are effective for such optimization and static program analysis methods have been used. The static methods, however, have several problems such as the preciseness, the overestimation, etc. In this paper, we describe a program analysis method based on abstract interpretation and its application for datapath optimization., Information Processing Society of Japan (IPSJ), JapaneseAutomated Competitive Analysis of Online Problems (Evolutionary Advancement in Fundamental Theories of Computer Science)
Masanishi Shingo, Horiyama Takashi, Iwama Kazuo, RIMS Kokyuroku, 1375, 68, 77, May 2004
Kyoto University, EnglishBusy Outfielder Problem (New Aspects of Theoretical Computer Science)
Sakuma Toshinori, Ono Hirotaka, Yamashita Masafumi, Asahiro Yuichi, Makino Kazuhisa, Horiyama Takashi, RIMS Kokyuroku, 1325, 8, 14, May 2003
Kyoto University, JapaneseArea Efficient FPGA Architecture with Logic Function Folding
KAJIHARA Hirotsugu, NAKANISHI Masaki, HORIYAMA Takashi, KIMURA Shinji, WATANABE Katsumasa, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2003, 7, 37, 42, 28 Jan. 2003
The paper describes an area efficient FPGA architecture based on LUTs with logic function folding. Each LUT is a 3-1 LUT but is enhanced to implement a full adder function with only one LUT. The area of our 3-1 LUT is about 56 % compared to that of a simple 4-1 LUT. In the paper, we measure not only the LUT area but also the area of routing resource. We adopt the well-known island style-architecture for the routing mechanism, and find that the total FPGA area can be saved up to 32.4 % and on average 12 % by the experiments on several benchmark circuits compared to FPGA architecture based on 4-1 LUTs., Information Processing Society of Japan (IPSJ), JapaneseLUT Architecture for Adder/Subtractor Based on Folding of Logic Functions
Ishii Atsushi, Kajihara Hirotsugu, Nakanishi Masaki, Horiyama Takashi, Kimura Shinji, Watanabe Katsumasa, Proceedings of the IEICE General Conference, 2002, 104, 104, 07 Mar. 2002
The Institute of Electronics, Information and Communication Engineers, JapaneseDeduction and Abduction with Ordered Binary Decision Diagrams (Foundations of Computer Science)
Horiyama Takashi, Ibaraki Toshihide, RIMS Kokyuroku, 1148, 175, 180, Apr. 2000
Kyoto University, EnglishOrdered Binary Decision Diagrams Representing Knowledge-Bases (Models of Computation and Algorithms)
Horiyama Takashi, Ibaraki Toshihide, RIMS Kokyuroku, 1093, 93, 98, Apr. 1999
Kyoto University, EnglishKnowledge-Base Representation and Recognition of Positive/Horn Functions on Ordered Binary Decision Diagrams
HORIYAMA T., Technical Report of IEICE, 98, 17, 24, 1999An Exponential Lower Bound of the Size of OBDDs Representing Division
堀山 貴史, 矢島 脩三, 全国大会講演論文集, 53, 175, 176, 04 Sep. 1996
The size of an OBDD largely depends on the variable ordering. It is important to clarify the lower bounds of OBDDs representing arithmetic functions. In this report, we investigate a lower bound of the size of OBDDs representing integer division. More precisely, we focus on each bit of the output of the n-bit / n-bit division, and prove that the size of OBDDs representing the i-th bit is Ω(2^<(n-2)/8>). We also prove the same lower bound on ∨V-OBDDs, ∧-OBDDs and ⊕ -OBDDs. To prove this lower bound, we introduce a strong fooling set, which has a more restricted property than a fooling set., EnglishAffiliated academic society
Research Themes
- Exploration of Crystal Surface Structures through Enumeration of Discrete Structures on an Infinite Plane and Similarity Design
Grants-in-Aid for Scientific Research
01 Apr. 2023 - 31 Mar. 2028
久保山 哲二, 草場 彰, 堀山 貴史, 宇野 毅明, 平田 耕一
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Gakushuin University, 23H03461 - 組合せ剛性工学の実現に向けた理論基盤構築
科学研究費助成事業
01 Apr. 2024 - 31 Mar. 2027
東川 雄哉, 加藤 直樹, 照山 順一, 堀山 貴史, Sljoka Adnan, 安田 修悟, 小林 祐貴
日本学術振興会, 基盤研究(B), 兵庫県立大学, 23K28040 - 組合せ剛性工学の実現に向けた理論基盤構築
科学研究費助成事業
01 Apr. 2023 - 31 Mar. 2027
東川 雄哉, 加藤 直樹, 照山 順一, 堀山 貴史, Sljoka Adnan, 安田 修悟, 小林 祐貴
日本学術振興会, 基盤研究(B), 兵庫県立大学, 23H03350 - タイリング理論と分子科学の協働によるウイルス外殻構造の新たな設計原理の探究
科学研究費助成事業
30 Jun. 2023 - 31 Mar. 2026
松永 康佑, 舘 知宏, 堀山 貴史
日本学術振興会, 挑戦的研究(萌芽), 埼玉大学, 23K18105 - 列挙や数え上げなどを統一的に扱うための基盤技術
科学研究費助成事業
01 Apr. 2022 - 31 Mar. 2026
堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕
列挙、数え上げ、サンプリングなどのアルゴリズムは、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。ここで、同じ制約条件のもとで、つまり同じ解空間において、解の列挙、数え上げなどタイプの異なるアルゴリズムそれぞれを個別に設計する状況を見つめ直し、アルゴリズム設計者が頭の中に持つ解空間に関する理解をもとにアルゴリズムを導出する過程を明らかにすることで、列挙、数え上げ、サンプリングなどのアルゴリズム設計を統一的に扱うための指針を与えることを本研究課題の目的としている。
本研究課題の研究者のみならず、課題外の連携研究者との議論も通して、列挙や数え上げなどのアルゴリズム設計の過程の再検討を行った。具体的には、たとえば、グラフの同型性の観点から代表元のみを列挙する同型性の除去について、ZDD (Zero-Suppressed Binary Decision Disgrams; 零抑制型二分決定グラフ) を用いるアプローチの検討を行った。制約条件を満たす解集合をうまく区分し、それらの区分された解集合相互の関係を表す方法を検討する際に、非同型なものを漏れなく重複なく求められる保証を与える必要があり、具体的なアルゴリズム設計を通して、アルゴリズム設計とアイデア記述に関する知見を得た。また、列挙と深い関連を持つ組合せ遷移問題も含めて、関連分野への応用に関する検討を行った。具体的には、たとえば、45度系格子パターン上での折り紙の展開図の列挙と数え上げの技法についてである。この問題では、縦横および斜め45度方向の格子上のみに折り線の位置を限定し、各頂点で平坦に折ることのできる局所平坦性を制約として、展開図の列挙または数え上げを行っている。また、格子の規則性から、回転および鏡映反転による同型性を考慮する必要があり、応用上の要請だけでなく、本研究課題の方向性にも沿った研究成果である。
日本学術振興会, 基盤研究(B), 北海道大学, 23K24806 - 列挙や数え上げなどを統一的に扱うための基盤技術
科学研究費助成事業 基盤研究(B)
01 Apr. 2022 - 31 Mar. 2026
堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕
日本学術振興会, 基盤研究(B), 北海道大学, 22H03549 - Optimization of cell three-dimensional structure by computational origami and cell origami
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
01 Apr. 2022 - 31 Mar. 2025
繁富 香織, 上原 隆平, 堀山 貴史
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 22H01423 - Research Initiatives on Algorithmic Foundations for Social Advancement
Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (A)
19 Nov. 2020 - 31 Mar. 2025
湊 真一, 宇野 毅明, 安田 宜仁, 堀山 貴史, 河原林 健一, 山下 茂, 牧野 和久, 上原 隆平, 瀧本 英二, 玉置 卓
2020年度の4か月間は、研究領域全体の組織立ち上げ準備の期間として位置づけ、本研究領域の目標や活動の方向性に関する参加メンバの意識合わせ、階層的な組織構成の整備と定例会議体制の設定、メーリングリストやSNS等による内部連絡体制・文書共有システムの整備、研究領域のwebサイトの立ち上げと広報資料の作成、連携拠点オフィスの確保と必要な什器や機材の整備、事務系/技術系スタッフの必要人数の精査と採用、研究領域全体で利用する大型計算サーバなどの共用設備の精査と購入計画の策定実施、十分な応募件数の公募班を集めるための広報活動と審査体制の整備、本研究領域の外部評価者の人選と依頼、等の共通的な業務を実施した。
2020年度の研究領域全体に関わるイベントとしては、全ての計画班の代表者・分担者を対象とした「内部向けキックオフ領域集会」を12月9日に開催したこと、および本研究領域に関心を持つ可能性がある全ての研究者を対象として対外向けの「スタートアップシンポジウム」を1月7日に開催した他、新設した京都寺町三条サテライトラボや既存の東京神田サテライトラボと各研究者が所属する研究機関をリモートで接続する体制を整え、小規模な研究打合せや運営会議を必要に応じて随時実施した。これらの活動実績により本研究領域全体の情報交換を円滑に行う体制が整いつつある。
以上の活動は、新型コロナの感染状況に応じて、対面と遠隔を適切に組合わせながら実施した。
Japan Society for the Promotion of Science, Grant-in-Aid for Transformative Research Areas (A), Kyoto University, 20H05961 - Algorithmic Foundations Based on Large-Scale Discrete Structures
Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (A)
19 Nov. 2020 - 31 Mar. 2025
堀山 貴史, 湊 真一, 上原 隆平, 宇野 裕之, 竹田 正幸, 番原 睦則, 松井 泰子
情報化社会におけるデータの規模の拡大や組合せの複雑化などにより、理論と実用の両方の観点から、問題が内包する大規模離散構造を利用したアルゴリズムの設計技法が求められている。本研究では、これまで個別の分野において個々のアイデアに基づいて設計されてきたアルゴリズムの成功事例を理論計算機科学の観点から改めて観察することで、大規模離散構造を理解し、その構造をどのように利用しているかを整理する。このケースワークをもとに、指数関数的な壁に立ち向かうアルゴリズム設計のための方法論を新たに体系化することで、理論と実装が一体となって大規模離散構造処理のための革新的アルゴリズム基盤技術へと昇華することを目指している。このために、具体的には、二分決定グラフ (BDD; Binary Decision Diagram) やその亜種の零抑制型二分決定グラフ (ZDD; Zero-suppressed BDD) のアルゴリズム、逆探索による列挙アルゴリズム、グラフ探索アルゴリズム、文字列処理アルゴリズム、論理式の充足可能性判定問題 (SAT; satisfiability problem) の充足解探索アルゴリズムなどの、指数関数的に大きな解空間を持つ問題における場合分けや数え上げ、列挙、索引化などが必要とされる分野を対象に、ケースワークを始めた。ここには、計算量理論の観点から、解を求めるための計算複雑さだけでなく、遷移問題も視野に入れている。こうした取り組みとして、具体的には、たとえば、与えられた点集合に対して自己交差のない多角形を求める単純多角形化問題において、逆探索の観点からの列挙だけでなく、ZDD 構築に用いられるフロンティア法の設計技法に着想を得て、問題の解空間の構造を把握する試みなどがある。
Japan Society for the Promotion of Science, Grant-in-Aid for Transformative Research Areas (A), Hokkaido University, 20H05964 - Research on Integrated Techniques of Enumeration and Optimization Based on Discrete Structure Manipulation Systems
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
01 Apr. 2020 - 31 Mar. 2025
湊 真一, 堀山 貴史, 瀧川 一学, 川原 純, 番原 睦則, 山口 勇太郎
本年度の研究実績の概要は以下の通りである。
(i) 列挙と最適化の統合的アルゴリズム技法の研究と体系化：グラフの最短路問題のように、組合せ問題のアイテムにコストが定義されているときに、コスト総和が所与の閾値以下となるような実行可能解を列挙することは、多くの実用的な応用を持つ汎用的で重要な問題である。このような一般的なコスト制約つき組合せ問題に対して、ZDDを用いて大量の解を高速に全列挙する手法を考案した。実験の結果、実用的な規模の例題に対して、数百万通りの解集合を表すZDDを1秒以内で構築することができた。本研究結果は研究代表者自らが筆頭著者として国内研究会で発表し、今後、国際会議または論文誌での発表を目指して準備を進めている。
(ii) 離散構造処理系の基盤アルゴリズムの実装とソフトウェアの整備：BDD/ZDDをベースとする離散構造処理系のアルゴリズムは、原則として「BDDパッケージ」と呼ばれるソフトウェアライブラリとして公開されている。今年度に開発した高速列挙アルゴリズムの実装もこのパッケージに追加し、整備を進めている。
(iii) 関連分野との連携および応用分野への発展：ERATOや基盤(S)プロジェクトで形成された研究者コミュニティを可能な範囲で維持し、研究者が集まり最新の技術情報を交換する「場」を確保することを目的として、2020年9月17日に「基盤(A) プロジェクト近況報告＆自由討論会」と呼ぶオンラインワークショップを企画した。最終的に48名の研究者が参加して活発な討論が行われ、研究者コミュニティの活性化に貢献した。
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), Kyoto University, 20H00605 - タイリングによるウイルス外殻のボトムアップ設計
科学研究費助成事業 挑戦的研究(萌芽)
30 Jul. 2020 - 31 Mar. 2023
松永 康佑, 舘 知宏, 堀山 貴史
本研究はウイルス外殻の構造について、Casper and Klugの準等価理論による展開図を近似して正二十面体を作るアプローチとは対照的に、そもそも球面上を敷き詰めることのできる部品構造(コートタンパク構造)のパターンは何か?というタイリングの観点からウイルス外殻を調べ、外殻構造の構成とデザイン原理の理解を深化させることを目的とする。去年度は球面上のタイリングについて考察し、平面を埋め尽くすためのタイリング理論でわかっている部品構造の対象軸のうち6回対称軸を5回対称軸とみなすことで正二十面体のタイリングへと近似することを考案した。これを用いて準等価理論でT1に分類される外殻構造を観察したところ、外見上は4つの異なるタイリングへ分類できることがわかった。本年度は、去年度に主に外見だけで行ったT1外殻構造のタイリング分類を更に定量化するための研究を行った。まず一つ目に、外殻を構成するコートタンパク質モノマーの不斉炭素原子のデカルト座標を点群として発生させ、去年考案した正二十面体のタイリングを満たす平面を点群へフィッティングし分類するプログラムを開発した。実際に、T1外殻構造の一つのテストデータを定量的に分類できるようになった。二つ目として、剛体ドッキングプログラムを用いてコートタンパクのホモ二量体のドッキング計算を行い、得られたドッキングスコアとホモ二量体のスクリュー軸の関係を調べた。あるT1外殻構造では、スクリュー軸が3回対称軸と2回対称軸となるホモ二量体構造のスコアの成績が良かった一方で、別のT1外殻構造では5回対称軸と2回対称軸の成績が良かった。これは考案したタイリング分類の傾向と一致しており、タイリング分類が単なる見た目の分類だけでなく、構造の安定性とも関わっていることが示唆された。
日本学術振興会, 挑戦的研究(萌芽), 埼玉大学, 20K21380 - Application of computational origami to formulation of cells
Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Research (Pioneering)
01 Apr. 2020 - 31 Mar. 2022
Uehara Ryuhei
The purpose of this research was to construct a theoretical model for the construction of the three-dimensional structure of small-sized cells through experiments using actual cell origami, and to evaluate the foldability for cells. Under some conditions, cell folding experiments were performed. Based on these experimental results, we devised some model candidates that give a valid "foldability index" considering physical constraints. We are currently verifying the validity between the experimental data and the theoretical model we devised, and are preparing to publish it as a paper in the future. Especially from the mathematical aspect, it is considered that the greatest significance of this research is that we were able to construct a theoretical model that incorporates physical constraints to some extent.
Japan Society for the Promotion of Science, Grant-in-Aid for Challenging Research (Pioneering), Japan Advanced Institute of Science and Technology, 20K20311 - Research on the isomorphism for the enumeration of geometric figures
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
01 Apr. 2018 - 31 Mar. 2021
Horiyama Takashi
We focused on the isomorphism, which appears in various problems of computational geometry. We developed isomorphism-elimination algorithms for enumerating geometric objects, and applied the methodology to various fields. The enumeration by our proposed algorithms are based on BDDs (Binary Decision Diagrams) and ZDDs (Zero-suppressed BDDs). By combining the algorithms with the enumeration algorithms with the frontier-method, which is the framework for constructing BDDs/ZDDs in the top-down manner, the enumeration achieves extremely fast speed and extremely small memory consumption. For example, experimental results show that the proposed method is more than 300 times faster and 3,000 times less memory than the conventional algorithm with only the frontier-method.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), 18K11153 - Interpolative Expansion of Quantum Protocol Theory
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
01 Apr. 2016 - 31 Mar. 2021
Takeshi Koshiba
The computational power of the DQC1 model, which is a formalization of non-universal quantum computation with initialization-hard quantum states, is shown to be superior to classical computation. Many quantum distributed algorithms are developed. Under the standard model for distributed algorithms, efficient quantum protocols for several fundamental problems such as the shortest path problem. Secure quantum delegated computation cannot achieve the perfect security for classical clients. By introducing the notion of rewards in quantum computations, classical verification of having the quantum power of the server is affirmatively settled. This is a game-theoretic solution and gives a novel method in quantum computation.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), 16H01705 - Research on Fundamental Algorithms of Discrete Structure Manipulation Systems
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (S)
29 May 2015 - 31 Mar. 2020
MINATO Shin-ichi
In this project, we aimed to construct the core algorithms for discrete structure manipulation systems, and to provide efficient software tools for many researchers in various application areas. Our achievements include that (1) we first succeeded in enumerating all connected sub-block patterns (in total 109.8 billion patterns) of 47 prefectures in Japan, the data is open for all Japanese citizens from the governmental statistics center, and (2) we produced many academic papers, accepted at the top-conferences such as AAAI, WWW, KDD, INFOCOM, AISTATS, SDM, etc.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (S), 15H05711 - Establishment of intuitive geometry and promotion of its cooperation in computer science, architectural engineering, and mathematics education
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
10 Jul. 2015 - 31 Mar. 2019
Jin-ichi Itoh
We got results balanced well as follows for (A) continuous folding of polyhedron, (B) cooperation with architectural engineering, (C) cooperation with mathematical education, (D) establishment of intuitive geometry.
(A) We discovered some new continuous flat folding of polyhedra and extent it the union of 2D surfaces of high dimensional several regular polytopes. (B) It was shown to change Coxeter's regular skew polyhedra to have rigidity. (C) Several meeting on mathematics education was held to demonstrate the usefulness of intuitive geometry, and to develop teaching materials using dynamic geometry software. (D) The meeting "intuitive geometry" was continued, and the recognition of the name "intuitive geometry" could be improved. In addition, We have advanced several research that can be called intuitive geometry.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), 15KT0020 - Enumeration of geometric figures and its application
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
01 Apr. 2015 - 31 Mar. 2018
Horiyama Takashi
The methodology for designing enumeration algorithms of geometric objects are discussed by integrating basic technologies (e.g., BDDs (Binary Decision Diagrams), ZDDs (Zero-suppressed BDDs) and reverse search). We also applied the methodology to various fields. First, we focused on enumerating the developments of orthogonal boxes. We introduced the notion of unit square development, and proposed an efficient algorithms for constructing ZDDs of the unit square developments. We also considered the problem from the reverse side. That is, we proposed algorithms checking whether a given orthogonal polygon can be folded into an orthogonal box (and giving the creases if possible). As for the application of our method, we have enumerated all patterns of partitions for elections within a disparity bound, and also all rhombille tilings.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), Saitama University, 15K00008 - A Multifaced Approach Toward Understanding the Limitations of Compuation
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
28 Jun. 2012 - 31 Mar. 2017
Watanabe Osamu, ASANO Takao, IBARAKI Toshihide, IMAI Hiroshi, TODA Seinosuke, MARUOKA Akira, MINATO Shinichi, MAKINO Kazuhisa, KAWARABAYASHI Kazuhisa, ASANO Tetsuo, KATOH Naoki, AVIS David, TOKUYAMA Takeshi, YAMASHITA Shigeru, TAKIMOTO Eiji, HORIYAMA Takashi, MORI Ryuhei
The purpose of this project is to manage, as a headquarter, the whole research project for exploring the limits of computation (in short, the ELC project). Deepening the understanding of computation is a key for developing yet stronger and new methods of using computation, and for this purpose, the ELC project investigates the limits of computation from various view points from a wide area of mathematical science. For obtaining significant advancements by such a multi-disciplinary approach, the collaboration of researchers in the world is necessary. The main task of this project is to prepare an appropriate environment for promoting such collaborations. For this, we invited many researchers, organized a good number of research workshops, and organized several international symposiums from small to large. We also organized tutorial seminars, fall schools, and group study sessions for promoting our research and fostering young researchers.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Tokyo Institute of Technology, 24106001 - Development towards innovative data structure utilizing methodology of limit of computation
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
28 Jun. 2012 - 31 Mar. 2017
Tokuyama Takeshi, SADAKANE Kunihiko, YAMANAKA Katsuhisa
Our project aimed at development of several new methodologies on innovative data structures for big-data analysis utilizing the methodologies proposed and developed in the ELC project. The major accomplishments are: 1. Development of compressed data structures with efficient search and update algorithms 2. Solutions of problems in the application areas of genome and social big-data analysis by using theoretical compressed data structures, 3. Development of several algorithms and methods on ZDD and its application to structure enumeration in geometry and chemistry, and 4. Development of new data clustering method named data polishing with applications. Those accomplishments leads to real applications and succeed to several new influential data analysis projects lead by members of the project.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Tohoku University, 24106007 - Approximate Computing to Cope with Imperfect Information from Growing Data Size
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
01 Apr. 2013 - 31 Mar. 2016
IWAMA KAZUO, AVIS David, MIYAZAKI Shuichi, TAMAKI Suguru, ITO Hiro, HORIYAMA Takashi, YOSHIDA Yuichi, OKAMOTO Kazuya, SETO Kazuhisa, KAWAHARA JUN
One of the main challenge in modern algorithm design is to cope with insufficient information.
In this study, we try to construct a general framework for design of approximation algorithms that can cope with insufficient information due to rapidly growing data size.
As a result, we give design and analysis of such algorithms for various problems in several fields such as graph problems, algorithmic game theory and randomized computation theory.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), Kyoto University, 25240002 - On the enumeration of geometric objects
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
01 Apr. 2012 - 31 Mar. 2015
HORIYAMA Takashi
The methodology for designing enumeration algorithms of geometric objects are discussed by integrating basic technologies (e.g., BDDs (Binary Decision Diagrams), ZDDs (Zero-suppressed BDDs) and reverse search). As for the enumeration of developments of polyhedra, the efficiency of the combined method with the frontier-based ZDD construction and a removal of isomorphic developments is shown. The extension of this method is discussed for enumerating general developments (i.e., developments obtained by cutting not only the edges but also faces) of polyhedra. Moreover, the counting method for essentially different developments of any polyhedron is proposed. We can count the number of non-isomorphic developments without enumerating the developments.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (C), Saitama University, 24500008 - Studies on Algorithms for Insufficient Spatial Information
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
2010 - 2012
IWAMA Kazuo, AVIS David, MIYAZAKI Shuichi, TAMAKI Suguru, ITO Hiro, KATOH Naoki, TOKUYAMA Takeshi, YAMASHITA Masafumi, WATANABE Osamu, HORIYAMA Takashi, KAWAHARA Jun, MORIZUMI Hiroki
One of the main challenge in modern algorithm design is to copewith insufficient information. In this study, we try to construct a general framework fordesign and evaluation of algorithms that can cope with insufficient spatial information. Asa result, we give design and analysis of such algorithms for various problems in severalfields such as graph problems, algorithmic game theory and randomized computationtheory.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), Kyoto University, 22240001 - Computer-Aided Analysis and Design of Algorithms
Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B)
2008 - 2010
HORIYAMA Takashi
This research project has the following three main results. (1) We have designed algorithms for enumerating Tsume-Shogi by the reverse method. As a result, we can prove the longest mating-moves for a given set of Shogi-pieces. (2) We have designed algorithms for generating fundamental domains of p4-tiling (i.e., the tiling by 4-fold rotation) and p6-tiling (i.e., the tiling by 6-fold rotation) based on the reverse search. (3) We have designed algorithms for enumerating the unfoldings of polyhedra. By enumerating all unfoldings and checking their overlapping, we have solved an open problem for hundreds of years : Is every edge-unfolding of Platonic solids nonoverlapping? The answer is yes!
Japan Society for the Promotion of Science, Grant-in-Aid for Young Scientists (B), Saitama University, 20700005 - Design and Analysis of Algorithms for Insufficient Information
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
2007 - 2009
IWAMA Kazuo, KATOH Naoki, ITO Hiro, MIYAZAKI Shuichi, TAMAKI Suguru, SUGIHARA Kokichi, TOKUYAMA Takeshi, YAMASHITA Masafumi, WATANABE Osamu, HORIYAMA Takashi
One of the main challenge in modern algorithm design is to cope with insufficient information (to complement information). In this study, we rigorously discuss the desirable property of such algorithms and try to construct a framework for it including design techniques and evaluation method. As a result, we obtain efficient algorithms in various fields such as online, network, matching, randomized, geometric and distributed algorithms.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), Kyoto University, 19200001 - 離散アルゴリズムの性能保証自動化パラダイム
科学研究費助成事業 若手研究(B)
2005 - 2007
堀山 貴史
情報化社会の大規模化と多様化は、計算機による処理能力の向上と処理対象への柔軟な適応によるところが大きい。これは、コンピュータの処理速度の向上に顕著に見られるハードウェアの進歩に加えて、ソフトウェアのアルゴリズム革新に支えられている。ここに、アルゴリズムの設計と性能保証があらゆる分野の基礎として重視されてきている。アルゴリズムの性能保証には、理論的な性能解析が必要不可欠であるが、アルゴリズム設計と同じく人手で行っており、設計者の職人芸的なセンスに依存するところが大きい。本研究の主題は、アルゴリズムの理論的性能解析に計算機を援用することにある。これにより、定型的作業の負荷を減らし、思考の抽象度を高めることによる生産性の向上が期待できる。
本年度は、アルゴリズム的ゲーム理論の立場から、オークションのアルゴリズムの性能解析に関して検討を行った。具体的には、音楽ファイルなどの複製コストが無視できるほど小さく無限供給可能な商品に対する1ラウンド秘密入札オークションを対象とし、誘因両立性を持つアルゴリズムを設計した。また、入札の最高額と最低額の比rに関する競合比解析を提案し、本アルゴリズムの競合比がln r+1となることを示した。同様の観点から既存アルゴリズムの競合比をrの関数として解析し、小さなrに関しては提案アルゴリズムの競合比が常に良いことを示した。
日本学術振興会, 若手研究(B), 17700014 - Research on modeling and algorithms for network problems
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Priority Areas
2004 - 2007
ITO Hiro, IWAMA Kazuo, MASUZAWA Toshimitsu, MIYAZAKI Shuichi, HORIYAMA Takashi
グラフは接続関係を表現する抽象モデルとして有用であり, 古くから盛んに研究されている数学的対象である. 本特定領域研究では, ネットワークや計算機上での問題をグラフ問題としてモデル化し, そのアルゴリズム開発の研究を行った. その結果、密な部分グラフ発見問題, 供給点配置問題, 頂点被覆問題, 巡回セールスマン問題, 自己安定化問題, 安定マッチング問題などの様々な実用的問題について, 効率的なアルゴリズムを得ることができた.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Priority Areas, Kyoto University, 16092215 - Studies on Diarete Algorithms with Guaranteed Quality based on Engineering Criteria
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
2004 - 2006
IWAMA Kazuo, ITO Hiro, MIYAZAKI Shuichi, HORIYAMA Takashi
Traditionally the quality of discrete algorithms has been evaluated mostly by their asymptotic running time. However, it is often pointed out that running time is not a suitable measure of quality for some applications. Recently various measures have been proposed to evaluate algorithms in many perspectives. For example, "approximation ratio" is used to evaluate approximation algorithms, where an approximation algorithm must efficiently compute reasonable solutions for hard combinatorial problems. Another example, "competitive ratio" is used to evaluate online algorithms, where in online computation an algorithm must decide how to act on incoming items of information without any knowledge of future inputs. Both measures play very important roles in current algorithm theory. In our research, we think these new measures for algorithms as "quality for engineering" and develop high performance algorithms with respect to this quality. We mainly study network algorithms, matching algorithms and satisfiability algorithms. The followings are representative results of our project.
There is an extension of stable matching problems, where ties and incomplete lists are allowed in preference lists. Finding maximum stable matchings in this setting is known to be NP-hard and (trivial) 2-approximation algorithm is also known. We show a 1.8-approximating algorithm for the problem, which first achieves the approximation ratio below 2 and improves the previous best ratio of 2-c/$\sqrt{n}$.
It is an important open question whether minimum vertex cover problems (VC) are approximable within 2-ε and it is widely believed that the answer is in the negative. We consider VC on dense graphs and show a 2 /(1+A/d) approximation algorithm, which greatly improves the ratio 2 for general graphs. Here A, (d) is a maximum (average, resp.) degree of an input graph. The result is tight in the sense that if an improvement is possible, then we would have 2-approximation algorithms for general graphs.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 16300002 - データの論理的解析に基づく効率的な知識獲得手法とその応用
科学研究費助成事業 若手研究(B)
2002 - 2004
堀山 貴史
情報化社会の発達にともない、クレジットカードや各種検査の結果などの多種多様なデータを、大量かつ容易に集めることができるようになってきている。このため、集められた膨大なデータからその傾向や規則性などの有用な情報を得ることを目的とした知識獲得の研究の重要性がさまざまな分野で指摘されている。本研究では、データと対応づけした論理関数を媒介として、データの持つ論理的内容を知識として抽出することを目指している。
今年度は、まず、二分決定グラフ(Ordered Binary Decision Diagrams)を知識表現の手段として用いた知識ベース処理について、計算複雑さに関する考察とアルゴリズム設計を行った。具体的には、OBDDを用いた手法では演繹(deduction)が任意の論理関数に対して線形時間で可能となることを示した。仮説推論(abduction)は任意の論理関数に対してはNP-hardとなるが、扱う関数をHorn関数に限定することで、仮説に任意のリテラルを取りえるような説明を求める多項式時間アルゴリズムを示した。また、証明システムの複雑さと密接に関連するHajos calculusに着目し、その平面グラフ版の問題について考察を行った。Hajos calculusは3彩色不能なグラフを生成する非決定性のプロセスである。本研究では、3彩色不能な平面グラフのみを生成できる生成則を2種類提案し、それぞれの規則の健全性と完全性を証明した。また、その規則間の多項式時間模倣性を示した。
また、自律学習機構を備えたハードウェアへの知識獲得手法の適用の基礎的な問題として、高位言語からハードウェア記述の自動合成を行う高位合成における、浮動小数点数のビット長最適化を扱った。誤差解析において正方向の誤差と負方向の誤差を独立して考慮し、また、非線形最適化ソルバーを利用してビット長最適化問題を解く手法を提案し、シミュレーションによる手法よりも良好な結果を得た。
日本学術振興会, 若手研究(B), 京都大学, 14780219 - High Quality Discrete Algorithms Based on Engineering Criteria
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
2001 - 2003
IWAMA Kazuo, MIYAZAKI Shuichi, ITO Hiro, OKABE Yasuo, HORIYAMA Takashi
Discrete algorithms have been evaluated by the unique measure 'asymptotic time complexity' for many cases. Recently, however, many other measures have been proposed, e.g., the approximation ratios for solving combinatorial problems approximately, and the competitive ratios for solving online problems in which we have no information on the future inputs. In this research, we studied these new measures as the criteria based on engineering requirements, and developed the methodologies for qualifying algorithms from this point of view.
As to the stable marriage problems, it is known to be solvable in polynomial time. We have generalized the problem, and proved that it is also solvable in polynomial time even when ties in the lists or incomplete lists are allowed. While we proved the intractability for the case both ties and incompleteness are allowed, we proposed an approximation algorithm that achieves an approximation ratio less than 2.
As to the satisfiability problems, we developed a 1.324^n algorithm for 3-SAT by complementarily combining two types of algorithms based on, the local search and the backtracking. We also considered condensing the density (i.e., the ratio of satisfying assignments to the 2^n assignments) of formulas.
Other research topics are as follows ; online algorithms, network algorithms, quantum algorithms.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 13480081 - Construction of a General Purpose Problem solving System by Metaheuristics
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
2001 - 2003
IBARAKI Toshihide, HORIYAMA Takashi, NONOBE Koji, YAGIURA Mutsunori, HAJIME Ase
Recently, problems encountered in real applications become more complicated and large-scaled. Among a wide variety of problem types, we focus on those problems whose core parts can be formulated as an optimization problem ; especially as a combinatorial (or discrete) optimization problem. Our goal is to develop a general-purpose problem solving system that can deal with combinatorial optimization problems. To achieve this, we have prepared a number of standard problems so that as many problems as possible can be written in one of their forms, and developed efficient, robust and flexible approximation algorithms, all of which are based on metaheuristics. Some of them are being used in practice, incorporated into production systems of companies. Our standard problems are listed below.
・CSP (Constraint Satisfaction Problem)
・MAXSAT (MAXimum SATisfiability problem)
・RCPSP (Resource Constrained Project Scheduling Problem)
・GAP (Generalized Assignment Problem), MRGAP (Multi-Resource GAP)
・SCP (Set Covering Problem)
・VRP (Vehicle Routing Problem)
・2PP (2-dimensional Packing Problem)
・1CSTP (1-dimensional Cutting STock Problem)
・2CSTP (2-dimensional Cutting STock Problem)
・FED (Feature Extraction from Data)
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 13558027 - Implementation of Adaptable Hardware and Software for Changing Environment
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
1999 - 2001
WATANABE Katsumasa, HORIYAMA Takashi, TAKAGI Kazuyosi, KIMURA Shinji, NAKANISHI Masaki
The aim of our research is how to construct adaptable hardware and software for changing environment. In design and implementat ion of new informat ion systems, we research about methods of const ruct ing re-configurable system depending on changing envi ronment from total view points of hardware and software.
Through 3 years, we studied at the fol lowing theoretical and practical aspects.
(1) From the view point of adaptable software, we propose about the representat ion and construct ion of act ive software, the spontaneity and extensibility of objects in conversational programming, and optimizing C compiler to generate optimum bit-length variables in VHDL. Then we implement some examples and show the effectiveness of our proposals.
(2) From the view point of adaptable hardware, as examples of LSI with re-configurability, we design and construct LSI of Java processor with abiliity to shorten the sequence of instructions dynamically, LSI to guess the eye track and LSI to determine the direct ion of face person-independently. These LSI have hardware oriented algorithms and give response in real time.
(3) About hardware synthesis and verification, we propose a new symbolic image computation algorithm based on BDD(Binary Decision Diagram) constrain operator. Then we show good performance and effectiveness of the algorithm to large scale circuits.
(4) From the view point of learning and knowledge acquirement for environmental adaptability, we propose a method based on OBDD(ordered BOD). Then we design the algorithms of mutual conversion between conventional character istic model and OBDD.
(5) We pay attention to quantum computation. Quantun computers can exploi t quantum paralleiism to recognize the dynamic characteristics of environment. Then we research non-deterministic quantum fin te automata (OFA) and compare OFA with the classical counterparts.
As results of the research, we get some mechanism for constructing systems with environmental adaptability in hardware and software totally.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), NARA INSTITUTE OF SCIENCE AND TECHNOLOGY, 11480068 - Solving Computationally Hard Problems by Metaheuristics
Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Priority Areas (B)
1998 - 2000
IBARAKI Toshihide, NONOBE Koji, HORIYAMA Takashi, YAGIURA Mutsunori, SHINANO Yuji
Recently, many types of metaheuristics based on local search, e. g., simulated annealing, genetic algorithm, and tabu search, have been proposed, and successfully applied to various combinatorial optimization problems. The objective of this research is to develop powerful general-purpose algorithms for combinatorial problems arising in real applications. To achieve this purpose, we developed metaheuristics algorithms for the following problems : (a) Weighted Constraint Satisfaction Problem, (b) Generalized Assignment Problem, (c) Resource Constrained Project Scheduling Problem, (d) Set Covering Problem, (e) Cutting Stock Problem, (f) Vehicle Routing Problem, (g) Rectangle Packing Problem, and others. These problems are representative combinatorial optimization problems, and their conventional formulations are rather simple. In our research, aiming at improving the applicability of algorithms, we extended these formulations so that more practical and complicated problems can be handled.
In designing algorithms, we adopted iterated local search and tabu search as the frameworks, and defined search space and neighborhoods carefully so as to attain better performance. We also incorporated some mechanisms that adaptively control program parameters during the search, which can reduce users' efforts to tune the parameters appropriately.
In computational experiments, we solved many benchmark instances, and succeeded to improve the best known values for many instances. As to practical problems, our codes could also find solutions of high quality in reasonable computational time. Some codes are already being used in practical applications.
Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Priority Areas (B), Kyoto University, 10205211 - -
Competitive research funding - -
Competitive research funding
