| 关于E0的Steiner邮路问题 |
| |
| 引用本文： | 谢政,肖予钦.关于E0的Steiner邮路问题[J].运筹学学报,2003,7(2):84-90. |
| |
| 作者姓名： | 谢政 肖予钦 |
| |
| 作者单位： | 1. 国防科技大学理学院,长沙,410073
2. 国防科技大学电子科学与工程学院,长沙,410073 |
| |
| 摘 要： | 给定图G＝(V，E，ω)，E0真包含于E是是一个指定通过的边子集，本文讨论了关于E0的Steiner邮路问题的特殊情况，即由E0导出的子图仅有两个连通分支．我们分别考虑了三种不同的情形，并给出了子闭迹消去算法和带限制的最短链算法，前者是一个基于整数规划的精确算法，而后者是一个近似算法．
|
| 关 键 词： | Steiner邮路问题 图 连通分支 子闭迹消去算法 最短链算法 连通图 Euler图 整数规划 最小权完美匹配问题 偶图 |
| 修稿时间： | 2002年2月4日 |
The Steiner Postman Problem of E0 |
| |
| ZHENG XIE.The Steiner Postman Problem of E0[J].OR Transactions,2003,7(2):84-90. |
| |
| Authors: | ZHENG XIE |
| |
| Abstract: | Given graph G = (V, E),it E_0 is the set of required edges to be traversed, this paper considers a special case of the Steiner Postman Problem,in which the subgraph GE0] has two connected branches. We respectively discuss three different cases and give the subtour-elimination algorithm and the restricted shortest-chain algorithm.The former is an accurate algorithm based on an integer program and the latter is an approximate one. |
| |
| Keywords: | OR the Steiner Postman Problem General-connected Branch the Subtour-elimination Algorithm the Restricted Shortest-chain Algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
