Hybrid Local Search for the Steiner Problem in Graphs

Hybrid Local Search for the Steiner Problem in Graphs
复制标题

图中斯坦纳问题的混合局部搜索

DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Renato F. Werneck
Renato F. Werneck
中科院分区：
--
文献类型：
--
作者：
M. P. D. Aragão;C. Ribeiro;Eduardo Uchoa;Renato F. Werneck

文献摘要

被引文献

相似文献

设G =（V;E）是一个连通无向图，其中V是节点集，E是边集.给定非负权重函数w：E！图中的Steiner问题（SPG）是指在图G的一个最小权连通子树中，求出一个包含X中所有端点的最小权连通子树. SPG的解是一棵Steiner最小树。在Steiner最小树中结束的非终结节点称为Steiner节点。
Let G = (V;E) be a connected undirected graph, where V is the set of nodes and E denotes the set of edges. Given a non-negative weight function w : E ! IR + associated with its edges and a subset X V of terminal nodes, the Steiner problem in graphs (SPG) consists in nding a minimum weighted connected subtree of G spanning all terminal nodes in X. The solution of SPG is a Steiner minimum tree. The non-terminal nodes that end up in the Steiner minimum tree are called Steiner nodes.