论文研究 适当圆梯形图上生成树的最优并行算法

给定具有n个顶点和m个边的简单图G，生成树问题是为给定图G查找生成树。该问题有很多应用，例如电力系统，计算机网络设计和电路分析。 对于一个简单的图，可以使用CRCW PRAM上的O（m + n）个处理器在O（log n）时间内解决生成树问题。 通常，已知可以通过限制图的类别来开发更有效的并行算法。 在本文中，我们将提出一种并行算法，该算法在EREW PRAM上用O（n / log n）个处理器运行O（log n）时间，以构建适当的圆形梯形图。