.png){kind=icon}
返回
A probabilistic algorithm for Optimal Linear Arrangements
.png){kind=icon}
PRE
AI
DOI：10.1016/j.dam.2026.05.001.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
最优线性排列（OLA）问题旨在寻求一种图的顶点排序，以最小化边长之和，这是图布局中的一个基本挑战，并应用于超大规模集成电路设计、网络优化和数据可视化。我们提出了一种基本的随机算法，并利用条件期望方法对其进行了改进，从而推导出具有保证性能界限的确定性算法。我们的理论分析包括一个集中结果，表明对于随机图，最优OLA值集中在随机排列的期望值附近。此外，我们将问题扩展到加权图，并通过实证评估证明了我们算法的有效性。（c）2026年Elsevier B.V.保留所有权利，包括文本和数据挖掘、AI训练及类似技术的权利。
Keyword:
Linear arrangement
Graph
Random graph
Derandomization
Integer linear programming
Method of conditional expectations
期刊
D
IF:
1.1
论文数:
352
被引数:
7.7K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容