Improved Approximation of Layout Problems on Random Graphs
Improved Approximation of Layout Problems on Random Graphs作者机构：School of Mathematics and Statistics Carleton University Ottawa ON Canada Department of Mathematics University of California San Diego La Jolla CA USA
出 版 物：《Open Journal of Discrete Mathematics》 (离散数学期刊（英文）)
年 卷 期：2020年第10卷第1期
页 面：13-30页
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：Graph Arrangements Random Graphs Approximation Algorithms Undirected Graphs Directed Acyclic Graphs
摘 要：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.
维普期刊数据库