Geodesic
About searching for antipodal vertexes in symmetric Cayley graphs
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 1, pp. 86-99.

Voir la notice de l'article provenant de la source Math-Net.Ru

We present the antipodality relation and search for an antipodal vertex. We also give a randomized algorithm solving the oracle problem in symmetric Cayley graphs over group $\mathbb Z_2^n$. The number of queries is polynomial over the graph's degree. Ill. 1, bibliogr. 5.
Keywords: graph, antipodality
Mots-clés : automorphism, oracle. 
@article{DA_2015_22_1_a5,
     author = {I. M. Khuziev},
     title = {About searching for antipodal vertexes in symmetric {Cayley} graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {86--99},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_1_a5/}
}
TY  - JOUR
AU  - I. M. Khuziev
TI  - About searching for antipodal vertexes in symmetric Cayley graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 86
EP  - 99
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_1_a5/
LA  - ru
ID  - DA_2015_22_1_a5
ER  - 
%0 Journal Article
%A I. M. Khuziev
%T About searching for antipodal vertexes in symmetric Cayley graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 86-99
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_1_a5/
%G ru
%F DA_2015_22_1_a5
I. M. Khuziev. About searching for antipodal vertexes in symmetric Cayley graphs. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 1, pp. 86-99. http://geodesic.mathdoc.fr/item/DA_2015_22_1_a5/

[1] V. Yu. Krasin, “On the weak isometries of the Boolean cube”, J. Appl. Ind. Math., 1:4 (2007), 463–467 | DOI | MR | Zbl

[2] M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge Univ. Press, Cambridge, 2000 | MR | Zbl

[3] Childs A. M., Cleve R., Deotto E., Farhi E., Gutmann S., Spielman D. A., “Exponential algorithmic speedup by quantum walk”, Proc. 35th ACM Symp. Theory of Computing, STOC 2003 (San Diego, CA, USA, June 9–11, 2003), ACM, New York, 2003, 59–68 | MR | Zbl

[4] Kempe J., “Discrete quantum walks hit exponentially faster”, Proc. 7th Int. Workshop Randomization and Approximation Techniques in Computer Science, RANDOM'03 (Princeton, NJ, USA, Aug. 24–26, 2003), Lect. Notes Comput. Sci., 2764, eds. S. Arora, K. Jansen, J. D. P. Rolim, A. Sahai, Springer-Verl., Berlin, 2003, 354–369 | DOI | MR | Zbl

[5] Khuziev I., Quantum walk in symmetric Cayley graph over $\mathbb Z_2^n$, Cornell Univ. Libr. e-Print Archive, 2013, arXiv: 1305.6849