Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9500049 | Linear Algebra and its Applications | 2018 | 19 Pages |
Abstract
A circulant graph G is a graph on n vertices that can be numbered from 0 to nâ1 in such a way that, if two vertices x and (x+d) mod n are adjacent, then every two vertices z and (z+d) mod n are adjacent. We call layout of the circulant graph any numbering that witness this definition. A random circulant graph results from deleting each edge of G uniformly with probability 1âp. We address the problem of finding the layout of a random circulant graph. We provide a polynomial time algorithm that approximates the solution and we bound the error of the approximation with high probability.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Sebastian Richter, Israel Rocha,