Improved Approximation of Layout Problems on Random Graphs

• 作者: Kevin K. H. Cheung Patrick Girardet
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: GRAPH ARRANGEMENTS Random GRAPHS APPROXIMATION ALGORITHMS Undirected GRAPHS Directed ACYCLIC GRAPHS
• 年，卷（期）: 2020,（1）
• 页码范围: 13-30
• 页数: 18页
• 分类号: O15

摘要

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.