• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Improved Approximations for Tour and Tree Covers
【24h】

Improved Approximations for Tour and Tree Covers

机译：改进的游览和树木覆盖率近似值

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

摘要

A tree (tour) cover of an edge-weighted graph is a set of edges which forms a tree (closed walk) and covers every other edge in the graph. Arkin et al. give approximation algorithms with ratios 3.55 (tree cover) and 5.5 (tour cover). We present algorithms with a worst-case ratio of 3 for both problems.
机译：边缘加权图的树（游览）封面是一组边，它们形成一棵树（闭合步道）并覆盖图中的所有其他边。 Arkin等。给出比率为3.55（树覆盖）和5.5（游览覆盖）的近似算法。对于这两个问题，我们提出的最坏情况比率为3的算法。

著录项

  • 来源
    《Algorithmica》 |2004年第3期|p. 441-449|共9页
  • 作者

    Jochen Konemann; Goran Konjevod; Ojas Parekh; Amitabh Sinha;

  • 作者单位

    Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA15213-3890, USA;

    Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA;

    Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA;

    Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

    approximation algorithms; graph algorithms; network design;

    机译：逼近算法;图算法;网络设计;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号