...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Approximating the maximum 2- and 3-edge-colorablesubgraph problems
【24h】

Approximating the maximum 2- and 3-edge-colorablesubgraph problems

机译：逼近最大2和3边可着色子图问题

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

摘要

For a fixed value of a parameter k ≥ 2, the Maximum k-Edge-Colorable Subgraph Problemconsists in finding k edge-disjoint matchings in a simple graph, with the goal of maximisingthe total number of edges used. The problem is known to be APX-hard for all k, but thereexist polynomial time approximation algorithms with approximation ratios tending to 1as k tends to infinity. Herein we propose improved approximation algorithms for the casesof k 2 and k = 3, having approximation ratios of 5/6 and 4/5, respectively.
机译：对于参数k≥2的固定值，最大k边可着色子图问题包括在简单图中查找k个边不相交的匹配，目的是最大化使用的边总数。对于所有k，已知问题都是APX难题，但是存在多项式时间近似算法，其近似比率趋于1，因为k趋于无穷大。在此，我们针对k 2和k = 3的情况提出了改进的近似算法，其近似比率分别为5/6和4/5。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号