単体的複体のshellability判定

スポンサーリンク

概要

• 論文の詳細を見る

• shellabilityは組合せ分割と呼ばれる性質の1つで, 上限値問題や凸包形成において重要な概念として知られている.通常の場合, 単体的複体のshellability判定にはfacet数の階乗時間を要する.そこで, 個々の単体的複体に対応するh-assignmentという新しい概念を定義し, h-assignmentのshellability判定をfacetの線形時間で判定可能とするアルゴリズムを与える.つまり, 単体的複体のshellability判定は適切なh-assignmentの生成に依存する.そこで, ある性質を満たすdivisionというfacetの部分集合を定義し, 単体的複体をdivision集合に分割することで, 適切なh-assignmentを効率よく生成するアルゴリズムも提案する.

• 一般社団法人情報処理学会の論文
• 2001-09-25

著者

• 森山 園子

  東京大学大学院 理学系研究科 情報科学専攻 今井浩研究室 修士課程2年

関連論文

• 双二次最終多項式による有向マトロイドの実現不可能性判定
• Non-LP orientations, non-line shellings, and non-representable oriented matroids
• 最小包含球問題から得られる4-cubeグラフの向きづけ
• 単体的複体のshellability判定

スポンサーリンク