• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >Maximum Series-Parallel Subgraph
【24h】

Maximum Series-Parallel Subgraph

机译：最大串并联子图

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

摘要

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n—1 edges and any series-parallel graph on n vertices has at most 2n—3 edges. We present a 7/12-approximation for this problem and results showing the limits of our approach.
机译：考虑给定一个简单图G的NP难问题，以找到具有最大边数的G的串平行子图。给定一个连通图G，输出G的生成树的算法是1/2逼近。实际上，如果n是G中的顶点数，则G中的任何生成树都具有n-1个边，并且n个顶点上的任何串并联图最多具有2n-3个边。我们提出了这个问题的7/12近似值，结果表明了我们方法的局限性。

著录项

  • 来源
  • 会议地点 Montpellier(FR);Montpellier(FR)
  • 作者

    Gruia Calinescu; Cristina G. Fernandes; Hemanshu Kaul;

  • 作者单位

    Department of Computer Science, Illinois Institute of Technology, Chicago, IL60616, USA;

    Department of Computer Science, University of Sao Paulo, Rua do Matao, 101005508-090 Sao Paulo, Brazil;

    Department of Applied Mathematics, Illinois Institute of Technology, Chicago, I60616, USA;

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

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号