-
- HAMA Vitor Mitsuo FUKUSHIGUE
- Department of Mathematical Informatics, Nagoya University
-
- KANAZAWA Shogo
- Department of Mathematical Informatics, Nagoya University
-
- HU Yannan
- Department of Applied Mathematics, Tokyo University of Science
-
- IMAHORI Shinji
- Faculty of Science and Engineering, Chuo University
-
- ONO Hirotaka
- Department of Mathematical Informatics, Nagoya University
-
- YAGIURA Mutsunori
- Department of Mathematical Informatics, Nagoya University
Abstract
<p>In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed. The task is to find a placement of a set of gears called sub-gears, to connect every target gear to the torque generator source so that every target gear rotates in a given direction. The objective is to minimize the number of sub-gears to be used. We prove that the GPP is NP-hard by giving a reduction from the Hamiltonian path problem on 3-regular planar graphs, which is known to be NP-complete, to the GPP. We also present an upper bound for the number of sub-gears to be placed.</p>
Journal
-
- Journal of Advanced Mechanical Design, Systems, and Manufacturing
-
Journal of Advanced Mechanical Design, Systems, and Manufacturing 14 (5), JAMDSM0069-JAMDSM0069, 2020
The Japan Society of Mechanical Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390285300171665152
-
- NII Article ID
- 130007868078
-
- ISSN
- 18813054
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed