Reduction tests for the prize-collecting Steiner problem

被引：18

作者：

Uchoa, E ^{[1
]}

机构：

[1] Univ Fed Fluminense, Dept Prod Engn, BR-24210 Niteroi, RJ, Brazil

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 04期

关键词：

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 条

[1] PROBLEM REDUCTION METHODS AND A TREE GENERATION ALGORITHM FOR THE STEINER NETWORK PROBLEM
BALAKRISHNAN, A
PATEL, NR
[J]. NETWORKS, 1987, 17 (01) : 65 - 85
[2] AN ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS
BEASLEY, JE
[J]. NETWORKS, 1984, 14 (01) : 147 - 159
[3] Local search with perturbations for the prize-collecting Steiner tree problem in graphs
Canuto, SA
Resende, MGC
Ribeiro, CC
[J]. NETWORKS, 2001, 38 (01) : 50 - 58
[4] DEARAGAO MP, 2001, ELECT NOTES DISCRETE, V7
[5] Duin C, 1993, THESIS U AMSTERDAM
[6] REDUCTION TESTS FOR THE STEINER PROBLEM IN GRAPHS
DUIN, CW
VOLGENANT, A
[J]. NETWORKS, 1989, 19 (05) : 549 - 567
[7] Johnson DS, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P760
[8] Klau GW, 2004, LECT NOTES COMPUT SC, V3102, P1304
[9] Koch T, 1998, NETWORKS, V32, P207, DOI 10.1002/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO
[10] 2-O

← 1 2 →