Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Sebastian Richter, Israel Rocha: LAYOUT OF RANDOM CIRCULANT GRAPHS

## 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