Definition and algorithms for reliable steiner tree problem

被引：0
作者：
Yaohua Tang
Wenguo Yang
Tiande Guo
机构：
[1] University of Chinese Academy of Sciences,School of Mathematics
来源：
Journal of Systems Science and Complexity | 2015年 / 28卷
关键词：
Approximation algorithm; exact algorithm; reliability; steiner tree;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper considers a new form of the Steiner tree problem that is more practical and reliable, which we call Reliable Steiner Tree (RST) problem. The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it. The definition is based on the reliability of full components instead of Steiner vertices. The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree. The exact algorithm designed for this problem utilizes a dynamic programming frame. The approximationalgorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.
引用
收藏
页码：876 / 886
页数：10
相关论文
共 17 条
  • [1] Takahashi H.(1980)An approximate solution for the Steiner problem in graphs Math. Jap. 24 573-577
  • [2] Matsuyama A.(1993)An 11/6-approximation algorithm for the network Steiner problem Algorithmica 9 463-470
  • [3] Zelikovsky A.(1994)Improved approximations for the Steiner tree problem Journal of Algorithms 17 381-408
  • [4] Berman P.(1997)New approximation algorithms for the Steiner tree problems J. of Combinatorial Optimization 1 47-65
  • [5] Ramaiyer V.(2005)Tighter bounds for graph Steiner tree approximation SIAM J. Discrete Math 19 122-134
  • [6] Karpinski M.(1972)The Steiner problem in graphs Networks 1 195-207
  • [7] Zelikovsky A.(1994)A probably fast, provably optimal algorithm for rectilinear Steiner trees Random Structures and Algorithms 5 535-557
  • [8] Robins G.(1999)Computing optimal rectilinear Steiner trees: A survey and experimental evaluation Discrete Applied Mathematics 90 161-171
  • [9] Zelikovsky A.(2000)On exact solutions for the rectilinear Steiner tree problem Part 1: Theoretical results Algorithmica 26 68-9
  • [10] Dreyfus S. E.(undefined)undefined undefined undefined undefined-undefined
12