首页> 外文期刊>Journal of Parallel and Distributed Computing >Parallel recognition algorithms for chordal_planar graphs and planar k-trees
【24h】

Parallel recognition algorithms for chordal_planar graphs and planar k-trees

机译:chordal_planar图和平面k树的并行识别算法

获取原文
获取原文并翻译 | 示例

摘要

This paper presents parallel algorithms for recognizing chordal-planar graphs and planar k-trees. Both the algorithms run in O(log(2) n) time using O(n + m) processors on a concurrent-read and concurrent-write (CRCW), parallel random access machine (PRAM) model, where n and in are, respectively, the number of nodes and edges in the graph. The novelty of our chordal-planar graph recognition algorithm lies in that it is based on an elegant structural characterization of chordal-planar graphs proposed in this paper. Moreover, it is simpler than separately testing chordality and planarity. Our planar k-trees recognition algorithm is based on a new characterization of k-trees presented in this paper. (c) 2005 Elsevier Inc. All rights reserved.
机译:本文提出了用于识别弦平面图和平面k树的并行算法。两种算法都使用O(n + m)处理器在并发读取和并发写入(CRCW)并行随机存取机(PRAM)模型上以O(log(2)n)的时间运行,其中n和in分别为分别是图中节点和边的数量。我们的弦平面图识别算法的新颖之处在于它基于本文提出的弦平面图的优美结构特征。此外,它比分别测试弦和平面度更简单。我们的平面k树识别算法基于本文提出的k树的新特征。 (c)2005 Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号