• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >A simple and fast parallel coloring for distance-hereditary graphs
【24h】

A simple and fast parallel coloring for distance-hereditary graphs

机译：距离遗传图的简单快速并行着色

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T/sub d/(|V|, |E|) and P/sub d/d(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M/sub d/. Our algorithm runs in O(T/sub d/(|V|, |E|)+log|V|) time using O(P/sub d/(|V|, |E|)+|V|/log|V|) processors on M/sub d/. The best known result for constructing a decomposition tree needs O(log/sup 2/ |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.
机译：在文献中，有很多顺序和并行算法可以解决距离遗传图上的问题。包含树和图形的两类众所周知的图形属于距离遗传图形。我们考虑距离遗传图上的顶点着色问题。令T / sub d /（| V |，| E |）和P / sub d / d（| V |，| E |）分别表示构造距离的分解树表示所需要的时间和处理器复杂度PRAM模型M / sub d /上的遗传图G =（V，E）。我们的算法使用O（P / sub d /（| V |，| E |）+ | V | / log在O（T / sub d /（| V |，| E |）+ log | V |）时间中运行| / V |）处理器位于M / sub d /。在CREW PRAM上使用O（| V | + | E |）处理器，构造分解树的最著名结果需要O（log / sup 2 / | V |）时间。如果提供分解树作为输入，我们可以在EREW PRAM上使用O（| V | / log | V |）处理器在O（log | V |）时间内解决问题。据我们所知，距离遗传图没有针对此问题的并行算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号