• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
【24h】

A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs

机译：有界树宽图最小生成毛虫问题的线性时间算法

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

摘要

We consider the Minimum Spanning Caterpillar Problem (MSCP) in a graph where each edge has two costs, spine (path) cost and leaf cost, depending on whether it is used as a spine or a leaf edge. The goal is to find a spanning caterpillar in which the sum of its edge costs is the minimum. We show that the problem has a linear time algorithm when a tree decomposition of the graph is given as part of the input. Despite the fast growing constant factor of the time complexity of our algorithm, it is still practical and efficient for some classes of graphs, such as outerplanar, series-parallel (K4 minor-free), and Halin graphs. We also briefly explain how one can modify our algorithm to solve the Minimum Spanning Ring Star and the Dual Cost Minimum Spanning Tree Problems.
机译：我们在图中考虑最小跨越毛毛虫问题（MSCP），其中每个边缘都有两个成本，即脊柱（路径）成本和叶成本，这取决于它是用作脊柱还是叶边缘。目标是找到一条履带式履带，其边际成本之和最小。我们表明，当图的树分解作为输入的一部分给出时，该问题具有线性时间算法。尽管我们的算法时间复杂度的常数快速增长，但对于某些类型的图，例如外平面图，串并（无K4小图）和Halin图，它仍然是实用且有效的。我们还将简要说明如何修改我们的算法以解决最小生成环星和双重成本最小生成树问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号