计算机通讯网络中的施泰纳树问题_计算机网络 第7版 pdf

　　Dingzhu Du 　　Steiner Tree Problems In 　　Computer Communication 　　Networks
　　2008，359pp
　　Hardback
　　ISBN9789812791443
　　
　　堵丁柱等著
　　经典的施泰纳（Steiner）树问题，它又被称为最小连接树问题，被定义为：在一个度量空间中，对给定的一个点集合，找出相互连接所有给定点的最短网络。这样的网络被称之为在给定集合上的施泰纳树。施泰纳树问题是最著名的组合最优化问题之一，它具有悠久的研究历史，可以认为它是费马问题的推广。由于许多重要的公开问题的提出，使得施泰纳树问题在20世纪90年代受到了更大的关注。其研究成果不仅对组合最优化近似算法设计与分析的一般理论，而且对包括VLSI设计在内的许多应用都产生了极大的影响。本书研究了有关施泰纳树问题所实现的三个重大突破，以及在过去15年里，施泰纳树在计算机通讯网络研究中的某些重要应用。它不仅论述了施泰纳树问题的某些新进展，而且讨论了各种组合优化方法，从而在理论与实践之间保持了平衡。
　　本书共有10章，分成3个部分。第一部分经典施泰纳树问题的基础；第二部分经典施泰纳树问题的变异；第三部分基于施泰纳树的问题。各章标题为：1.极小化方法与施泰纳比例；2.K�施泰纳比例及较佳的近似算法；3.几何划分与多项式时间；4.服务施泰纳问题的等级；5.最小施泰纳点的施泰纳树问题；6.瓶颈施泰纳树问题；7.施泰纳K�树与K�路径路由问题；8.施泰纳树着色问题；9.施泰纳树高度问题；10.可残存施泰纳网络问题。最后是附录A更多与施泰纳树相关的问题。
　　本书可供从事施泰纳树研究及应用的数学、计算机科学及工程专业的研究人员、研究生阅读。
　　胡光华，
　　高级软件工程师
　　(原中国科学院物理学研究所)
　　Hu Guanghua, Senior Software Engineer
　　(Former Institute of Physics,CAS)