| Autor: |
Vitor Mitsuo FUKUSHIGUE HAMA, Shogo KANAZAWA, Yannan HU, Shinji IMAHORI, Hirotaka ONO, Mutsunori YAGIURA |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vol 14, Iss 5, Pp JAMDSM0069-JAMDSM0069 (2020) |
| Druh dokumentu: |
article |
| ISSN: |
1881-3054 |
| DOI: |
10.1299/jamdsm.2020jamdsm0069 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
