The computational complexity of the gear placement problem
The computational complexity of the gear placement problem
复制标题
DOI：
10.1299/jamdsm.2020jamdsm0069
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vitor Mitsuo Fukushigue Hama;S. Kanazawa;Yannan Hu;S. Imahori;Hirotaka Ono;M. Yagiura
中科院分区：
文献类型：
--
作者：
Vitor Mitsuo Fukushigue Hama;S. Kanazawa;Yannan Hu;S. Imahori;Hirotaka Ono;M. Yagiura
本文分析了齿轮啮合问题（GPP）的复杂性。在GPP中，我们给出一个称为齿轮箱的矩形平面，在该平面上放置了一个扭矩发生器源和一组称为目标齿轮的齿轮。任务是找到一组称为子齿轮的齿轮的位置，将每个目标齿轮连接到扭矩发生器源，以便每个目标齿轮在给定方向上旋转。目标是尽量减少要使用的子齿轮的数量。通过将已知为np完全的3正则平面图上的哈密顿路径问题简化为GPP，证明了GPP是np困难的。我们还给出了要放置的子齿轮数目的上界。
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.