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. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11672142_31 | STACS |
Keywords | Field | DocType |
hypergraph isomorphism,graph isomorphism,certain specific bound,bounded color class,vertex set,arbitrary size,polynomial-time algorithm,computational complexity | Graph theory,Discrete mathematics,Combinatorics,Graph isomorphism,Vertex (graph theory),Hypergraph,Isomorphism,Time complexity,Mathematics,Bounded function,Computational complexity theory | Conference |
Volume | ISSN | ISBN |
3884 | 0302-9743 | 3-540-32301-5 |
Citations | PageRank | References |
5 | 0.43 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
V. Arvind | 1 | 52 | 4.34 |
Johannes Köbler | 2 | 580 | 46.51 |