首页> 外文会议>Computing and combinatorics >Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs
【24h】

Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs

机译:有界图的近似分布式最小顶点覆盖算法

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

摘要

In this paper, two distributed algorithms for the minimum vertex cover problem are given. In the unweighted case, we propose a 2.5-approximation algorithm with round complexity O(A), where A is the maximal degree of G, improving the previous 3-approximation result with the same round complexity O(A). For the weighted case, we give a 4-approximation algorithm with round complexity O(A).
机译:本文给出了两种最小顶点覆盖问题的分布式算法。在未加权的情况下,我们提出了一种具有圆形复杂度O(A)的2.5逼近算法,其中A是G的最大程度,以相同的圆形复杂度O(A)改进了先前的3逼近结果。对于加权情况,我们给出了具有圆形复杂度O(A)的4近似算法。

著录项

  • 来源
    《Computing and combinatorics》|2010年|p.100-109|共10页
  • 会议地点 Nha Trang(VN);Nha Trang(VN);Nha Trang(VN)
  • 作者单位

    College of Mathematics and Computer Science, Hebei University, China,Department of Computer Science, The University of Hong Kong, Hong Kong;

    Department of Computer Science, The University of Hong Kong, Hong Kong;

    Department of Computer Science, The University of Hong Kong, Hong Kong;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号