带权外平面图线性布局的并行算法

THE PARALLEL ALGORITHM OF WEIGHTED OUTER PLANAR GRAPH LINEAR LAYOUT PROBLEM

本文对整数赋权的外平面图的总边长线性布局问题给出多项式算法，并且在ＣＲＥＷ－ＰＲＡＭ并行计算模型下给出了并行算法，其在Ｏ（δｎ２）台处理机上需时Ｏ（ｌｏｇ２ｎ）

This paper presents efficient algorithms of total length linear layout graph problem of interal weighted outer planar graph, specially, the parallel algorithm of this problem, whose complexity is O( log 2n) on O(δn 2) processors under CREW-PRAM parallel computing model.