Deciding Shellability of Simplicial Complexes with h-Assignments
Deciding Shellability of Simplicial Complexes with h-Assignments
复制标题
DOI：
10.1587/transfun.e94.a.1238
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
Sonoko Moriyama
中科院分区：
文献类型：
--
作者：
Sonoko Moriyama
如果一个d维纯单纯复形C有一个壳，这是C的所有刻面的一个特定的全序，则C被称为可壳的。我们考虑的问题，决定是否C是可壳或没有。这个问题在m的线性时间内解决，m是C的所有面的数量，如果d=1或C是d=2的伪流形。否则，此时不知道是否可以在m的多项式时间内解决可壳性的判定。因此，对于后一种情况，我们别无选择，只能将蛮力方法应用于决策问题;即检查m！看看是否可以将C的所有m个面排列成一个壳。本文在C语言中引入了一个新的概念--h-赋值，并提出了一种利用h-赋值判断C语言是否可壳的实用方法。该方法可以用比蛮力法更小的计算量来判定C的可壳性。
If a d-dimensional pure simplicial complex C has a shelling, which is a specific total order of all facets of C, C is said to be shellable. We consider the problem of deciding whether C is shellable or not. This problem is solved in linear time of m, the number of all facets of C, if d=1 or C is a pseudomanifold in d=2. Otherwise it is unknown at this point whether the decision of shellability can be solved in polynomial time of m. Thus, for the latter case, we had no choice but to apply a brute force method to the decision problem; namely checking up to the m! ways to see if one can arrange all the m facets of C into a shelling. In this paper, we introduce a new concept, called h-assignment, to C and propose a practical method using h-assignments to decide whether C is shellable or not. Our method can make the decision of shellability of C by smaller sized computation than the brute force method.