Sebastian Richter, Israel Rocha: LAYOUT OF RANDOM CIRCULANT GRAPHS

Author(s):

Sebastian Richter
Israel Rocha

Title:

Sebastian Richter, Israel Rocha: LAYOUT OF RANDOM CIRCULANT GRAPHS

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 02, 2017

Mathematics Subject Classification:

    05C50 []
    05C85 []
    15A52 []
    15A18 []

Abstract:

A circulant graph $H$ is defined on the set of vertices $V=\left\{ 1,\ldots,n\right\} $ and edges $E=\left\{ \left(i,j\right):\left|i-j\right|\equiv s\left(\textrm{mod}n\right),s\in S\right\} ,$ where $S\subseteq\left\{ 1,\ldots,\lceil\frac{n-1}{2}\rceil\right\} .$ A random circulant graph results from deleting edges of $H$ with probability $1-p$. We provide a polynomial time algorithm that approximates the solution to the minimum linear arrangement problem for random circulant graphs. We then bound the error of the approximation with high probability

Keywords:

Random graphs, Geometric graphs, Circulant Matrices, Random Matrices, Rank correlation coefficient

Language:

English

Publication time:

7/2017