...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Efficient Algorithms for k-Terminal Cuts on Planar Graphs
【24h】

Efficient Algorithms for k-Terminal Cuts on Planar Graphs

机译：平面图上k末端切割的高效算法

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

摘要

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n~2log n logm), O(m~2 n~(1.5)log~2 n + kn)} time algorithm with a (2–2/k)-approximation ratio (clearly, m ≤ k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(nk~3 +(n logn)k~2) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(kn~2logn) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m ≤ k).
机译：最小的k端子切割问题具有相当大的理论意义，并且出现在几个应用领域，例如并行和分布式计算，VLSI电路设计和联网。在本文中，我们针对n个顶点无向加权平面图G给出了针对该问题的两种新的逼近算法和精确算法。对于k个终端覆盖G的m> 1个面的边界的情况，我们给出min { O（n〜2log n logm），O（m〜2 n〜（1.5）log〜2 n + kn）}时间算法，其近似比为（2–2 / k）（m≤k）。对于所有k个终端都被G的一个面的边界覆盖的情况，我们给出O（nk〜3 +（n logn）k〜2）时间精确算法，或者如果k = 3，则给出线性时间精确算法，用于计算最佳的k端切割。我们的算法基于有趣的观察，并在将其应用于平面图时对其进行了改进。据我们所知，以前没有专门解决平面图中k端割问题的近似算法。 Dahlhaus等人的（2–2 / k）逼近算法。 （对于一般图形）应用于平面图形需要O（kn〜2logn）时间。我们对平面图的近似算法比Dahlhaus等人的算法运行得更快。至少乘以O（k / logm）因子（m≤k）。

著录项

  • 来源
    《Algorithmica》 |2004年第2期|p. 299-316|共18页
  • 作者

    Danny Z. Chen; Xiaodong Wu;

  • 作者单位

    Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA;

    Department of Computer Science, University of Texas – Pan American, 1201 West University Drive, Edinburg, TX 78539, USA;

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

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号