Navigation

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

Presseartikel

  • MINT gewinnt

    Drei sächsische Hochschulen verfolgen unterschiedliche Konzepte, um Studieninteressenten Mathematik, Informatik, Naturwissenschaften und Technik schmackhaft zu machen …

  • Mathematik ganz alltagsnah

    „Videowoche der Mathematik“ zeigt das Fach von seiner spannenden, menschlichen und alltagstauglichen Seite …

  • Wahlzeit an der Universität

    Wahlvorschläge für Organe und Ämter an der TU Chemnitz können bis zum 23. Oktober 2017 eingereicht werden – Briefwahlanträge sind bis 27. Oktober 2017 zu stellen …