A note on decision versus search for graph automorphism

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