文献

J-GLOBAL ID：202002288456500702   整理番号：20A2114926

歯車配置問題の計算量

The computational complexity of the gear placement problem

著者 (6件)： 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)
資料名： Journal of Advanced Mechanical Design, Systems, and Manufacturing (Web)  (Journal of Advanced Mechanical Design, Systems, and Manufacturing (Web))
巻： 14  号： 5  ページ： JAMDSM0069(J-STAGE)  発行年： 2020年 
JST資料番号： U0027A  ISSN： 1881-3054  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,歯車配置問題(GPP)の複雑性を解析した。GPPでは,トルク発生源および目標歯車と呼ばれる歯車のセットを配置するギヤボックスと呼ばれる矩形平面が与えられている。タスクは,あらゆる目標歯車が与えられた方向に回転するように,あらゆる目標歯車をトルク発生源に接続するための,サブ歯車と呼ばれる歯車セットの配置を見つけることである。目的は,使用されるサブ歯車の数を最小化することである。GPPがNP困難であることを,NP完全であることが知られている3-正則平面グラフ上のハミルトニアン経路問題からのリダクションをGPPに与えることにより証明した。また,配置されるサブ歯車の数に対する上限も提示した。(翻訳著者抄録)

シソーラス用語： 歯車 ,  *配置問題 ,  *計算量 ,  NP困難 ,  歯車箱
準シソーラス用語： ギヤ ,  ギヤボックス

著者キーワード (4件)： 計算の複雑さ ,  歯車配置問題 ,  NP困難 ,  還元

分類 (1件)： 数値計算  (JE02000J)

引用文献 (12件)：

• Biedl, T. C., New lower bounds for orthogonal graph drawings, in F. J. Brandenburg (ed.), Graph Drawing, Vol. 1027 of Lecture Notes in Computer Science, Springer (1996), pp.28-39.
• Birgin, E. G. and Gentil, J. M., New and improved results for packing identical unitary radius circles within triangles, rectangles and strips, Computers & Operations Research, Vol.37, No.7 (2010), pp.1318-1327.
• Castillo, I., Kampas, F. J. and Pintér, J. D., Solving circle packing problems by global optimization: numerical results and industrial applications, European Journal of Operational Research, Vol.191, No.3 (2008), pp.786-802.
• Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), WH Freeman.
• Garey, M. R., Johnson, D. S. and Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM Journal on Computing, Vol.5, No.4 (1976), pp.704-714.

タイトルに関連する用語 (3件)： 歯車 ,  配置問題 ,  計算量