On Hypergraph and Graph Isomorphism with Bounded Color Classes
On Hypergraph and Graph Isomorphism with Bounded Color Classes
V. Arvind and Johannes Köbler
Abstract:
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
zuletzt geändert:
12.04.06
SV
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Seite bearbeiten
Deutsch
English