Díaz, J., Petit, J., Trevisan, L. and Serna, M. (2001) Approximating Layout Problems on Random Graphs. Discrete Mathematics, 235, 245-253.
https://doi.org/10.1016/S0012-365X(00)00278-8

has been cited by the following article:

• TITLE: Improved Approximation of Layout Problems on Random Graphs

  AUTHORS: Kevin K. H. Cheung, Patrick Girardet

  KEYWORDS: Graph Arrangements, Random Graphs, Approximation Algorithms, Undirected Graphs, Directed Acyclic Graphs

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.10 No.1, January 10, 2020

  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ös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.