DROPS

Document

Vertex reconstruction in Cayley graphs

Authors: Elena Konstantinova

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{konstantinova:DagSemProc.06201.11,
  author =	{Konstantinova, Elena},
  title =	{{Vertex reconstruction in Cayley graphs}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.11},
  URN =		{urn:nbn:de:0030-drops-7869},
  doi =		{10.4230/DagSemProc.06201.11},
  annote =	{Keywords: Reconstruction problems, Cayley graphs, the symmetric group, the signed permutation group, sorting by reversals, pancake problem}
}

Search Results

Documents authored by Konstantinova, Elena

Vertex reconstruction in Cayley graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message