Home >

news ヘルプ

論文・著書情報


タイトル
和文:極小剛なBody-Hingeグラフの列挙 : 2013年4月15日版(一般) 
英文: 
著者
和文: 小林 祐貴, 東川雄哉, 加藤直樹.  
英文: Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh.  
言語 Japanese 
掲載誌/書名
和文:電子情報通信学会技術研究報告. COMP, コンピュテーション 
英文: 
巻, 号, ページ Vol. 113    No. 50   
出版年月 2013年4月 
出版者
和文:一般社団法人電子情報通信学会 
英文: 
会議名称
和文: 
英文: 
開催地
和文: 
英文: 
アブストラクト 本論文は極小剛な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グラフあたり多項式時間で済む.

©2007 Institute of Science Tokyo All rights reserved.