Improved Approximation of Layout Problems on Random Graphs

• 作 者: Kevin K. H. Cheung Patrick Gir
• 出 处: 离散数学期刊(英文)
• 发表日期: 2020年1期
• 关键词: GRAPH ARRANGEMENTS Random GRAPHS APPROXIMATION ALGORITHMS Undirected GRAPHS Dire

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