Layout of random circulant graphs

DOI10.1016/J.LAA.2018.09.003MaRDI QIDQ1794318zbMATH OpenOpenAlexWikidataFDO

Authors Sebastian Richter, Israel Rocha

Publication date 15 October 2018

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.04480

zbMATH Keywords

random matricescirculant matricesrandom graphsgeometric graphsrank correlation coefficient

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52)

Abstract: A circulant graph H is defined on the set of vertices V=left{ 1,ldots,n ight} and edges E=left{ left(i,j ight):left|i-j ight|equiv sleft( extrm{mod}n ight),sin S ight} , where Ssubseteqleft{ 1,ldots,lceilfrac{n-1}{2} ceil ight} . 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.

Recommendations

• Approximating layout problems on random graphs
• Random walks and bisections in random circulant graphs
• Random walks, bisections and gossiping in circulant graphs
• Random circulant digraphs
• Recognizing circulant graphs in polynomial time: An application of association schemes

Cites work

• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• A Simple SVD Algorithm for Finding Hidden Partitions
• A useful variant of the Davis-Kahan theorem for statisticians
• Approximating layout problems on random geometric graphs
• Embeddings of circulant networks
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Mapping the genome
• Numerical Methods for Computing Angles Between Linear Subspaces
• Optimal Numberings of an $N \times N$ Array
• Recovering the structure of random linear graphs
• The Rotation of Eigenvectors by a Perturbation. III

Cited in

(4)

• Approximating layout problems on random graphs
• Recovering the structure of random linear graphs
• Random walks, bisections and gossiping in circulant graphs
• Random walks and bisections in random circulant graphs

This page was built for publication: Layout of random circulant graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1794318)