The Steiner Problem in Graphs
作者： Nelson Maculan
DOI: 10.1016/S0304-0208(08)73236-5
关键词: Combinatorics 、 Steiner tree problem 、 Euclidean geometry 、 Mathematics 、 Directed graph 、 Transformation (function) 、 Undirected graph 、 Integer programming 、 Discrete mathematics
摘要: Publisher Summary This chapter reviews formulations and some procedures that have been suggested for the solution of Steiner Problem in graphs. It presents definition results associated with classical also known as Euclidean (ESP). The discusses graphs where an undirected graph (SPUG) a directed (SPDG) are defined. transformation SPUG SPDG. provides overview on Lawler algorithm SPUG. chaptre four integer programming graphs, compares linear relaxations three these formulations, describes application Benders method to solve one illustrated by example. methods based computational results.
elsevier.com
sci-hub.se 参考文章(32)
Stephen Graves, Bezalel Gavish, Scheduling and Routing in Transportation and Distribution Systems: Formulations and New Relaxations ,(1981)
Joseph B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem Proceedings of the American Mathematical Society. ,vol. 7, pp. 48- 50 ,(1956) , 10.1090/S0002-9939-1956-0078686-7
A. Claus, A new formulation for the travelling salesman problem Siam Journal on Algebraic and Discrete Methods. ,vol. 5, pp. 21- 25 ,(1984) , 10.1137/0605004
Z.A. Melzak, On the Problem of Steiner Canadian Mathematical Bulletin. ,vol. 4, pp. 143- 148 ,(1961) , 10.4153/CMB-1961-016-2
Linus Schrage, Implicit representation of generalized variable upper bounds in linear programming Mathematical Programming. ,vol. 14, pp. 11- 20 ,(1978) , 10.1007/BF01588948
S. E. Dreyfus, R. A. Wagner, The steiner problem in graphs Networks. ,vol. 1, pp. 195- 207 ,(1971) , 10.1002/NET.3230010302
Y. P. Aneja, An integer linear programming approach to the steiner problem in graphs Networks. ,vol. 10, pp. 167- 178 ,(1980) , 10.1002/NET.3230100207
Robert W. Floyd, Algorithm 97: Shortest path Communications of The ACM. ,vol. 5, pp. 345- ,(1962) , 10.1145/367766.368168
J. E. Beasley, An algorithm for the steiner problem in graphs Networks. ,vol. 14, pp. 147- 159 ,(1984) , 10.1002/NET.3230140112
E. J. Cockayne, ON THE STEINER PROBLEM Canadian Mathematical Bulletin. ,vol. 10, pp. 431- 450 ,(1967) , 10.4153/CMB-1967-041-8