Agrawal, M. ; Arvind, V. (1996) A note on decision versus search for graph automorphism Proceedings of Eleventh Annual IEEE Conference on Computational Complexity . pp. 272-277. ISSN 1093-0159
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...
Related URL: http://dx.doi.org/10.1109/CCC.1996.507689
Abstract
We show that for any graph G, k non-trivial automorphisms of G-if as many exist-can be computed in time |G|O(log k) with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence we show that some problems related to GA and GI are polynomial-time truth-table equivalent to GA.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to IEEE. |
| ID Code: | 95350 |
| Deposited On: | 07 Nov 2012 05:24 |
| Last Modified: | 07 Nov 2012 05:24 |
Repository Staff Only: item control page
