Layout of Random Circulant Graphs

0494245 - ÚI 2019 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: Random graphs * Geometric graphs * Circulant matrices * Random matrices * Rank correlation coefficient
Obor OECD: Applied mathematics
Impakt faktor: 0.977, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0287472