计算机与数字工程2026，Vol.54Issue(2)：315-320,6.DOI:10.3969/j.issn.1672-9722.2026.02.003
Internal Steiner Tree问题的精确算法
Exact Algorithm for Internal Steiner Tree Problem
付振星 1宁爱兵 1曾宾 1张惠珍1
作者信息
- 1. 上海理工大学管理学院 上海 200093
- 折叠
摘要
Abstract
The Internal Steiner Tree Problem with wide application value is a branch of the classical Steiner tree problem.In this paper,the mathematical properties of Internal Steiner Tree Problem are proposed from several aspects,such as the relationship between nodes,the degree of nodes and the comparison of the weight of paths between nodes.These mathematical properties can re-duce the size of the problem by determining whether the nodes and edges that satisfy the conditions in the problem are or are not in the optimal solution.Then,based on the mathematical properties,this paper proposes a backtracking algorithm with reduction.At the same time,the upper and lower bound sub-algorithms are used to prune the solution space of the problem.Finally,an example is given to illustrate the steps of the algorithm,and then the complexity of the algorithm is analyzed.关键词
IST问题/数学性质/降阶/回溯Key words
Internal Steiner Tree Problem/mathematical properties/reduction/backtracking分类
数理科学引用本文复制引用
付振星,宁爱兵,曾宾,张惠珍..Internal Steiner Tree问题的精确算法[J].计算机与数字工程,2026,54(2):315-320,6.
