On the Complexity of Polytope Isomorphism Problems

被引：0

作者：

Volker Kaibel

Alexander Schwartz

机构：

[1] Technische Universität Berlin,

[2] Fakultät II,undefined

[3] Institut für Mathematik,undefined

[4] MA 6-2,undefined

[5] Straße des 17. Juni 136,undefined

[6] 10623 Berlin,undefined

[7] Germany e-mail: kaibel@math.tu-berlin.de,undefined

[8] Technische Universität Berlin,undefined

[9] Fakultät II,undefined

[10] Institut für Mathematik,undefined

[11] MA 6-2,undefined

[12] Straße des 17. Juni 136,undefined

[13] 10623 Berlin,undefined

[14] Germany e-mail: schwartz@math.tu-berlin.de,undefined

来源：

Graphs and Combinatorics | 2003年 / 19卷

关键词：

Key words. Polytope isomorphism, Equivalence of polytopes, Graph isomorphism complete, Graph isomorphism hard, Polytope congruence;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：215 / 230

页数：15