A note on decision versus search for graph automorphism

被引：7

作者：

Agrawal, M ^{[1
]}

Arvind, V ^{[1
]}

机构：

[1] INST MATH SCI, MADRAS 600113, TAMIL NADU, INDIA

来源：

INFORMATION AND COMPUTATION | 1996年 / 131卷 / 02期

关键词：

D O I：

10.1006/inco.1996.0097

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that for any graph G, k nontrivial 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 are actually polynomial-time truth-table equivalent to GA. One of these results provides an answer to an open question of Lubiw [SIAM J. Comput. 10 (1981), 11-21]. (C) 1996 Academic Press.

引用

页码：179 / 189

页数：11

共 12 条

[1] BALCAZAR JL, 1988, EATCS MONOGRAPHS THE, V1
[2] BALCAZAR JL, 1989, REV MAT COMPLUT, V2, P175
[3] DESIGNING PROGRAMS THAT CHECK THEIR WORK
BLUM, M
KANNAN, S
[J]. JOURNAL OF THE ACM, 1995, 42 (01) : 269 - 291
[4] FORTNOW L, 1993, UNPUB GRAPH AUTOMORP
[5] Harary F., 1969, GRAPH THEORY
[6] Hoffmann C. M., 1982, LECT NOTES COMPUTER, V136
[7] KOBLER J, 1992, GRAPH ISOMORPHISM IT
[8] LOZANO A, 1992, STRUCT COMPL TH CONF, P118, DOI 10.1109/SCT.1992.215387
[9] SOME NP-COMPLETE PROBLEMS SIMILAR TO GRAPH ISOMORPHISM
LUBIW, A
[J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (01) : 11 - 21
[10] NOTE ON THE GRAPH ISOMORPHISM COUNTING PROBLEM
MATHON, R
[J]. INFORMATION PROCESSING LETTERS, 1979, 8 (03) : 131 - 132

← 1 2 →