A CATALOG OF STEINER TREE FORMULATIONS

被引：90

作者：

GOEMANS, MX ^{[1
]}

MYUNG, YS ^{[1
]}

机构：

[1] DANKOOK UNIV,DEPT BUSINESS ADM,CHEONAN 330,SOUTH KOREA

来源：

NETWORKS | 1993年 / 23卷 / 01期

关键词：

D O I：

10.1002/net.3230230104

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem.

引用

页码：19 / 28

页数：10

共 31 条

[1] AN INTEGER LINEAR-PROGRAMMING APPROACH TO THE STEINER PROBLEM IN GRAPHS [J].

ANEJA, YP .

NETWORKS, 1980, 10 (02) :167-178

[2] A DUAL-ASCENT PROCEDURE FOR LARGE-SCALE UNCAPACITATED NETWORK DESIGN [J].

BALAKRISHNAN, A ;

MAGNANTI, TL ;

WONG, RT .

OPERATIONS RESEARCH, 1989, 37 (05) :716-740

[3] AN ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS [J].

BEASLEY, JE .

NETWORKS, 1984, 14 (01) :147-159

[4]

CHOPRA S, 1990, NODE WEIGHTED STEINE

[5]

CHOPRA S, 1988, SPANNING TREE POLYHE

[6]

CHOPRA S, 1988, STEINER TREE PROBLEM, V2

[7]

CHOPRA S, 1988, STEINER TREE PROBLEM, V1

[8]

Edmonds J, 1970, COMBINATORIAL STRUCT

[9]

Fulkerson D. R., 1974, Mathematical Programming, V6, P1, DOI 10.1007/BF01580218

[10]

Fulkerson D. R., 1971, MATH PROGRAM, V1, P168

← 1 2 3 4 →