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

THE PARALLEL ALGORITHM OF WEIGHTED OUTER PLANAR GRAPH LINEAR LAYOUT PROBLEM

作　　者：孙孝瑞[1] 邵峰晶[1] 

机构地区：[1]青岛大学计算机系

出　　处：《青岛大学学报（自然科学版）》1997年第1期44-48,共5页Journal of Qingdao University(Natural Science Edition)

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

关 键 词：外平面图 线性布局 并行计算 多项式算法 

分 类 号：O157.5[理学—数学]