Improved approximation of layout problems on random graphs
From MaRDI portal
Publication:6293140
arXiv1710.10339MaRDI QIDQ6293140FDOQ6293140
Authors: Kevin K. H. Cheung, Patrick D. Girardet 
Publication date: 27 October 2017
Abstract: Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs Discrete Mathematics, 235, 2001, 245--253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erd"os-Renyi distribution with appropriate sparsity conditions. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.
This page was built for publication: Improved approximation of layout problems on random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6293140)
