LEADER 04029nam 2200601Ia 450 001 9910782273603321 005 20230721032723.0 010 $a1-281-93394-5 010 $a9786611933944 010 $a981-279-145-0 035 $a(CKB)1000000000538158 035 $a(DLC)2008299551 035 $a(StDuBDS)AH24684965 035 $a(SSID)ssj0000251328 035 $a(PQKBManifestationID)11200076 035 $a(PQKBTitleCode)TC0000251328 035 $a(PQKBWorkID)10248367 035 $a(PQKB)11760696 035 $a(MiAaPQ)EBC1681725 035 $a(WSP)00001938 035 $a(Au-PeEL)EBL1681725 035 $a(CaPaEBR)ebr10255725 035 $a(CaONFJC)MIL193394 035 $a(OCoLC)815752225 035 $a(EXLCZ)991000000000538158 100 $a20080128d2008 uy 0 101 0 $aeng 135 $aur||||||||||| 181 $ctxt 182 $cc 183 $acr 200 10$aSteiner tree problems in computer communication networks$b[electronic resource] /$fDingzhu Du, Xiaodong Hu 210 $aSingapore ;$aHackensack, NJ $cWorld Scientific$dc2008 215 $a1 online resource (xiii, 359 p. )$cill 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a981-279-144-2 320 $aIncludes bibliographical references (p. 337-353) and index. 327 $a1. Minimax approach and Steiner ratio. 1.1. Minimax approach. 1.2. Steiner ratio in the Euclidean plane. 1.3. Steiner ratios in other metric spaces. 1.4. Discussions -- 2. k-Steiner ratios and better approximation algorithms. 2.1. k-Steiner ratio. 2.2. Approximations better than minimum spanning tree. 2.3. Discussions -- 3. Geometric partitions and polynomial time approximation schemes. 3.1. Guillotine cut for rectangular partition. 3.2. Portals. 3.3. Banyan and Spanner. 3.4. Discussions -- 4. Grade of service Steiner Tree problem. 4.1. GoSST problem in the Euclidean plane. 4.2. Minimum GoSST problem in graphs. 4.3. Discussions -- 5. Steiner Tree problem for minimal Steiner points. 5.1. In the Euclidean plane. 5.2. In the rectilinear plane. 5.3. In metric spaces. 5.4. Discussions -- 6. Bottleneck Steiner tree problem. 6.1. Complexity study. 6.2. Steinerized minimum spanning tree algorithm. 6.3. 3-restricted Steiner Tree algorithm. 6.4. Discussions -- 7. Steiner k-Tree and k-Path routing problems. 7.1. Problem formulation and complexity study. 7.2. Algorithms for k-Path routing problem. 7.3. Algorithms for k-Tree routing problem. 7.4. Discussions -- 8. Steiner Tree coloring problem. 8.1. Maximum tree coloring. 8.2. Minimum tree coloring. 8.3. Discussions -- 9. Steiner Tree scheduling problem. 9.1. Minimum aggregation time. 9.2. Minimum multicast time problem. 9.3. Discussions -- 10. Survivable Steiner network problem. 10.1. Minimum k-connected Steiner networks. 10.2. Minimum weak two-connected Steiner networks. 10.3. Minimum weak three-edge-connected Steiner networks. 10.4. Discussions. 330 $aThe Steiner tree problem is one of the most important combinatorial optimization problems. It has a long history that can be traced back to the famous mathematician Fermat (1601-1665). This book studies three significant breakthroughs on the Steiner tree problem that were achieved in the 1990's, and some important applications of Steiner tree problems in computer communication networks researched in the past fifteen years. It not only covers some of the most recent developments in Steiner tree problems, but also discusses various combinatorial optimization methods, thus providing a balance between theory and practice. 606 $aSteiner systems 606 $aComputer networks 615 0$aSteiner systems. 615 0$aComputer networks. 676 $a004.6 700 $aDu$b Dingzhu$061540 701 $aHu$b Xiaodong$01495488 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910782273603321 996 $aSteiner tree problems in computer communication networks$93719574 997 $aUNINA