Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

On Hypergraph and Graph Isomorphism with Bounded Color Classes

V. Arvind and Johannes Köbler

Abstract:

Using logspace counting classes we study the computational complexity of hypergraph and graph isomorphism where the vertex sets have bounded color classes for certain specific bounds. We also give a polynomial-time algorithm for hypergraph isomorphism for bounded color classes of arbitrary size.

PDF-File: On Hypergraph and Graph Isomorphism with Bounded Color Classes