Number of the records: 1
Layout of Random Circulant Graphs
- 1.0494245 - ÚI 2019 RIV US eng J - Journal Article
Richter, S. - Rocha, Israel
Layout of Random Circulant Graphs.
Linear Algebra and Its Applications. Roč. 559, 15 December (2018), s. 95-113. ISSN 0024-3795. E-ISSN 1873-1856
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Random graphs * Geometric graphs * Circulant matrices * Random matrices * Rank correlation coefficient
OECD category: Applied mathematics
Impact factor: 0.977, year: 2018
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.
Permanent Link: http://hdl.handle.net/11104/0287472
File Download Size Commentary Version Access 0494245pre2.pdf 1 1.1 MB arXiv.org Author´s preprint require
Number of the records: 1