Go backward to 22 Polytope Isomorphism
Go up to 4 Isomorphism
Go forward to 24 Selfduality of Polytopes
|
Go backward to 22 Polytope Isomorphism Go up to 4 Isomorphism Go forward to 24 Selfduality of Polytopes |
XHTML 1.0 |
| Input: | Vertex-facet incidence matrices AP and AQ of polytopes P and Q, respectively |
|---|---|
| Output: | "Yes" if AP can be transformed into AQ by row and column permutations, "No" otherwise |
| Status (general): | Graph isomorphism complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
The problem remains graph isomorphism complete even if
V- and H-descriptions of P and Q are
part of the input data [34].
In constant dimension the problem can be solved in polynomial time by a reduction [34] to the graph isomorphism problem for graphs of bounded degree, for which a polynomial time algorithm is known (Luks [41]). Problem 22 can polynomially be reduced to this problem. For polytopes of bounded dimension both problems are polynomial time equivalent. |
| Related problems: | 22, 21 |
|---|
|
|
Why are some symbols not displayed correctly? |