極小剛なBody-Hingeグラフの列挙（2013年4月15日版）

小林祐貴; 東川雄哉; 加藤直樹

論文・著書情報

タイトル

和文:	極小剛なBody-Hingeグラフの列挙（2013年4月15日版）
英文:

著者

和文:	小林祐貴, 東川雄哉, 加藤直樹.
英文:	Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh.

言語

Japanese

掲載誌/書名

和文:	研究報告アルゴリズム（AL）
英文:

巻, 号, ページ

Vol. 2013 No. 13

出版年月

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グラフあたり多項式時間で済む．

Home

各種検索

サポート

T2R2について

関連リンク

論文・著書情報