Reduction tests for the prize-collecting Steiner problem

被引:18
作者
Uchoa, E [1 ]
机构
[1] Univ Fed Fluminense, Dept Prod Engn, BR-24210 Niteroi, RJ, Brazil
关键词
Steiner problem; network design; preprocessing; combinatorial optimization;
D O I
10.1016/j.orl.2005.02.007
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This article introduces a proper redefinition of the concept of bottleneck Steiner distance for the prize-collecting Steiner problem. This allows the application of reduction tests known to be effective on Steiner problem in graphs in their full power. Computational experiments attest the effectiveness of the proposed tests. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:437 / 444
页数:8
相关论文
共 20 条