DagSemProc.06201.11.pdf
- Filesize: 246 kB
- 20 pages
Document
Vertex reconstruction in Cayley graphs
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6201
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-07
Cite As Get BibTex
Elena Konstantinova. Vertex reconstruction in Cayley graphs. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06201.11
Abstract
In this report paper we collect recent results on the vertex reconstruction in Cayley graphs $Cay(G,S)$. The problem is stated as the problem of reconstructing a vertex from the minimum number of its $r$-neighbors that are vertices at distance at most $r$ from the unknown vertex. The combinatorial properties of Cayley graphs on the symmetric group $Sn$ and the signed permutation group $Bn$ with respect to this problem are presented. The sets of generators of $S$ are specified by applications in coding theory, computer science, molecular biology and physics.
Subject Classification
Keywords
- Reconstruction problems
- Cayley graphs
- the symmetric group
- the signed permutation group
- sorting by reversals
- pancake problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads