On the Complexity of Polytope Isomorphism Problems
On the Complexity of Polytope Isomorphism Problems
复制标题
论多面体同构问题的复杂性
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Alexander Schwartz
中科院分区：
文献类型：
--
作者：
V. Kaibel;Alexander Schwartz
抽象的。 我们证明，决定两个（凸）多面体（由它们的顶点-面重合给出）是否组合同构的问题是图同构完全的，即使对于简单或单纯的多面体也是如此。另一方面，我们给出了有界维组合多面体同构问题的多项式时间算法。此外，我们得出结论，决定由顶点或面描述给出的两个多面体是否投影或仿射同构的问题是图同构困难的。
Abstract. We show that the problem to decide whether two (convex) polytopes, given by their vertex-facet incidences, are combinatorially isomorphic is graph isomorphism complete, even for simple or simplicial polytopes. On the other hand, we give a polynomial time algorithm for the combinatorial polytope isomorphism problem in bounded dimensions. Furthermore, we derive that the problems to decide whether two polytopes, given either by vertex or by facet descriptions, are projectively or affinely isomorphic are graph isomorphism hard.