極小剛なBody-Hingeグラフの列挙 : 2013年4月15日版(一般)

• 小林 祐貴

  京都大学大学院工学研究科

• 東川 雄哉

  京都大学大学院工学研究科

• 加藤 直樹

  京都大学大学院工学研究科

抄録

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている.3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが,その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている.剛体(body)を頂点,剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ.本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する.まず,所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し,この操作によりすべてのbody-hingeグラフが生成可能であることを証明する.これにより,すべてのbody-hingeグラフを生成するアルゴリズムを提案する.計算時間は一つのbody-hingeグラフあたり多項式時間で済む.

収録刊行物

• 電子情報通信学会技術研究報告. COMP, コンピュテーション

  電子情報通信学会技術研究報告. COMP, コンピュテーション 113 (50), 81-88, 2013-05-10

  一般社団法人電子情報通信学会

詳細情報

• CRID: 1572261552787243008
• NII論文ID: 110009768646
• NII書誌ID: AN10013152
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles