Agrawal, M. ; Arvind, V. (1996) A note on decision versus search for graph automorphism Information and Computation, 131 (2). pp. 179-189. ISSN 0890-5401
![[img]](http://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Author Version
224kB |
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1006/inco.1996.0097
Abstract
We show that for any graphG,knontrivial automorphisms ofG-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 are actually polynomial-time truth-table equivalent to GA. One of these results provides an answer to an open question of Lubiw [Lu 81].
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 92031 |
| Deposited On: | 26 May 2012 13:52 |
| Last Modified: | 19 May 2016 05:37 |
Repository Staff Only: item control page
