• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Annals of "Dunarea de Jos" University of Galati, Fascicle III, Electrotechnics, Electronics, Automatic Control, Informatics >COUNTING MINIMUM COST BOUNDED DEGREE SUBTREES IN GRAPHS WITH SMALL 2-VERTEX-CONNECTED COMPONENTS
【24h】

COUNTING MINIMUM COST BOUNDED DEGREE SUBTREES IN GRAPHS WITH SMALL 2-VERTEX-CONNECTED COMPONENTS

机译：在带有2个顶点连接的小部件的图形中计算最小成本绑定度子级

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we present new algorithms for counting minimum cost bounded degree subtrees in connected graphs in which the 2-vertex-connected (biconnected) components have small sizes. The 2-vertex-connected components and the cut vertices can be organized into a block-cut vertex tree which is also a tree decomposition with small width of the graph. We present a dynamic programming algorithm which is very efficient on this particular tree decomposition and we also discuss methods of solving the problem given an arbitrary tree decomposition with small width. Among some of the most important results is an algorithm which can efficiently compute the number of subtrees of a (small) graph corresponding to each possible degree sequence.
机译：在本文中，我们提出了新的算法，用于计算连接图（其中2个顶点连接（双向）组件的大小较小）中的最小成本有界度子树。可以将2个顶点连接的组件和切出的顶点组织成块切出的顶点树，该树也是具有较小图形宽度的树分解。我们提出了一种动态编程算法，该算法对这种特定的树分解非常有效，并且我们还讨论了在给定宽度较小的任意树分解的情况下解决问题的方法。在一些最重要的结果中，有一种算法可以有效地计算与每个可能的度数序列相对应的（小）图的子树数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号