Vertex reconstruction in Cayley graphs

Author Elena Konstantinova



PDF
Thumbnail PDF

File

DagSemProc.06201.11.pdf
  • Filesize: 246 kB
  • 20 pages

Document Identifiers

Author Details

Elena Konstantinova

Cite AsGet 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.
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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail