The computational complexity of the gear placement problem

• 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

抄録

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.

収録刊行物

• Journal of Advanced Mechanical Design, Systems, and Manufacturing

  Journal of Advanced Mechanical Design, Systems, and Manufacturing 14 (5), JAMDSM0069-JAMDSM0069, 2020

  一般社団法人 日本機械学会

キーワード

• Computational complexity
• Gear placement problem
• NP-hard
• Reduction

詳細情報

• CRID: 1390285300171665152
• NII論文ID: 130007868078
• DOI: 10.1299/jamdsm.2020jamdsm0069
• ISSN: 18813054
• Web Site: https://www.jstage.jst.go.jp/article/jamdsm/14/5/14_2020jamdsm0069/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可