Name
Abstract | ||
|---|---|---|
In this paper we study the complexity of Bounded Color Multiplicity Graph Isomorphism BCGIb: the input is a pair of vertex-colored graphs such that the number of vertices of a given color in an input graph is bounded by b.We show that BCGIb is in the #L hierarchy (more precisely, the ModkL hierarchy for some constant k depending on b). Combined with the fact that Bounded Color Multiplicity Graph Isomorphism is logspace many-one hard for every set in the ModkL hierarchy for any constant k, we get a tight classification of the problem using logspace-bounded counting classes. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/CCC.2005.7 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | ISSN |
vertex-colored graph,color multiplicity graph isomorphism,tight classification,isomorphism bcgib,logspace many-one,bounded color multiplicity graph,constant k,modkl hierarchy,l hierarchy,input graph,graph isomorphism,polynomials,computational complexity,parallel algorithms,galois fields,computational modeling | Journal | 1093-0159 |
ISBN | Citations | PageRank |
0-7695-2364-1 | 5 | 0.45 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Piyush P. Kurur | 2 | 88 | 9.41 |
| T. C. Vijayaraghavan | 3 | 19 | 3.54 |