,TRANSFORMATIONS FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM AND THE MAXIMUM-WEIGHT CONNECTED SUBG

来源 :计算数学(英文版) | 被引量 : 0次 | 上传用户:berg123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.
其他文献
Poisson-Nest-Planck equations are widely used to describe the electrodiffusion of ions in a solvated biomolecular system.Two kinds of two-grid finite element al
We propose new numerical schemes for decoupled forward-backward stochastic differential equations (FBSDEs) with jumps,where the stochastic dynamics are driven b
教科书中的删减之风由来已久,编者的理由大致有三个:一是内容不合适,删除糟粕或有时代局限性的内容;二是形式不完美,并不是好文章处处皆好,可能会有一些不够完美的地方;三是理解有难
This paper is conceed with the problem of scattering of time-harmonic electromagnetic waves from penetrable diffraction gratings in the 2D polarization case.We
“刷——刷——”粉笔在黑板上移动,渐渐地,越变越短,越变越短,成了粉笔头,但它却为同学们创造了一个无比广阔的知识天地。那一行行字就是它描绘出的知识的天地和海洋,它就像
期刊
翠翠是沈从文先生1934年写的小说《边城》的主人公,苏教版高中语文第二册必修二第四专题节选了其中的第三章至第六章的内容。在教读这篇小说时,由于时空的限制,学生难以理解作者
本论文以三得利紫花苜蓿为材料,采用正交实验设计和单因素实验设计相结合的方法,研究了紫花苜蓿愈伤组织诱导和分化过程中不同的外植体类型和基础培养基类型、以及不同外源生长调节物质对紫花苜蓿愈伤组织诱导和分化的影响,从而建立一套高效的紫花苜蓿组织培养再生体系。实验结果如下:1.紫花苜蓿愈伤组织诱导的最佳外植体为下胚轴,最适宜的基础培养基为MS基础培养基,最优的外源激素组合和浓度为2mg/L 2,4-D+0
期刊