LEADER 06494nam 22008535 450 001 9910437871803321 005 20200630075539.0 010 $a1-4614-5242-2 024 7 $a10.1007/978-1-4614-5242-3 035 $a(CKB)2670000000299665 035 $a(EBL)1030657 035 $a(OCoLC)819816599 035 $a(SSID)ssj0000799483 035 $a(PQKBManifestationID)11510633 035 $a(PQKBTitleCode)TC0000799483 035 $a(PQKBWorkID)10764057 035 $a(PQKB)10295268 035 $a(DE-He213)978-1-4614-5242-3 035 $a(MiAaPQ)EBC1030657 035 $a(MiAaPQ)EBC6312578 035 $a(PPN)168302462 035 $a(EXLCZ)992670000000299665 100 $a20121026d2013 u| 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aConnected Dominating Set: Theory and Applications /$fby Ding-Zhu Du, Peng-Jun Wan 205 $a1st ed. 2013. 210 1$aNew York, NY :$cSpringer New York :$cImprint: Springer,$d2013. 215 $a1 online resource (205 p.) 225 1 $aSpringer Optimization and Its Applications,$x1931-6828 ;$v77 300 $aDescription based upon print version of record. 311 $a1-4899-8714-2 311 $a1-4614-5241-4 320 $aIncludes bibliographical references (pages [193]-199) and index. 327 $aConnected Dominating Set:Theory and Applications; Preface; Contents; Chapter1 Introduction; 1.1 Connected Domination Number; 1.2 Virtual Backbone in Wireless Networks; 1.3 Converter Placement in Optical Networks; 1.4 Connected Domatic Number; 1.5 Lifetime of Sensor Networks; 1.6 Theory and Applications; Chapter2 CDS in General Graph; 2.1 Motivation and Overview; 2.2 Complexity of Approximation; 2.3 Two-Stage Greedy Approximation; 2.4 Weakly CDS; 2.5 One-Stage Greedy Approximation; 2.6 Weighted CDS; 2.7 Directed CDS; Chapter3 CDS in Unit Disk Graph; 3.1 Motivation and Overview 327 $a3.2 NP-Hardness and PTAS3.3 Two-Stage Algorithm; 3.4 Independent Number (I); 3.5 Independent Number (II); 3.6 Zassenhaus-Groemer-Oler Inequality; Chapter 4 CDS in Unit Ball Graphs and Growth Bounded Graphs; 4.1 Motivation and Overview; 4.2 Gregory-Newton Problem; 4.3 Independent Points in Two Balls; 4.4 Growth-Bounded Graphs; 4.5 PTAS in Growth-Bounded Graphs; Chapter5 Weighted CDS in Unit Disk Graph; 5.1 Motivation and Overview; 5.2 Node-Weighted Steiner Tree; 5.3 Double Partition; 5.4 Cell Decomposition; 5.5 6-Approximation; 5.6 4-Approximation; 5.7 3.63-Approximation; Chapter6 Coverage 327 $a9.4 A Two-Staged Algorithm for Min-CDSChapter10 Geometric Hitting Set and Disk Cover; 10.1 Motivation and Overview; 10.2 Minimum Geometric Hitting Set; 10.3 Minimum Disk Cover; Chapter11 Minimum-Latency Scheduling; 11.1 Motivation and Overview; 11.2 Geometric Preliminaries; 11.3 Dominating Tree; 11.4 Broadcast Scheduling; 11.5 Aggregation Scheduling; 11.6 Gathering Scheduling; 11.7 Gossiping Scheduling; Chapter12 CDS in Planar Graphs; 12.1 Motivation and Overview; 12.2 Preliminaries; 12.3 Algorithm Description; 12.4 Performance Analysis; References; Index 330 $aThe connected dominating set (CDS) has been a classic subject studied in graph theory since 1975. It has been discovered in recent years that CDS has important applications in communication networks ?especially in wireless networks ?as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. This work is a valuable reference for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, industrial engineering, and discrete mathematics. The book may also be used as a text in a graduate seminar for PhD students. Readers should have a basic knowledge of computational complexity and combinatorial optimization. In this book, the authors present the state-of-the-art in the study of connected dominating sets. Each chapter is devoted to one problem, and consists of three parts: motivation and overview, problem complexity analysis, and approximation algorithm designs. The text is designed to give the reader a clear understanding of the background, formulation, existing important research results, and open problems. Topics include minimum CDS, routing-cost constrained CDS, weighted CDS, directed CDS, SCDS (strongly connected dominating set), WCDS (weakly connected dominating set), CDS-partition, virtual backbone in wireless networks, convertor placement in optical networks, coverage in wireless sensor networks, and more. 410 0$aSpringer Optimization and Its Applications,$x1931-6828 ;$v77 606 $aOperations research 606 $aManagement science 606 $aAlgorithms 606 $aCombinatorics 606 $aComputer communication systems 606 $aMathematical optimization 606 $aOperations Research, Management Science$3https://scigraph.springernature.com/ontologies/product-market-codes/M26024 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aCombinatorics$3https://scigraph.springernature.com/ontologies/product-market-codes/M29010 606 $aComputer Communication Networks$3https://scigraph.springernature.com/ontologies/product-market-codes/I13022 606 $aOptimization$3https://scigraph.springernature.com/ontologies/product-market-codes/M26008 615 0$aOperations research. 615 0$aManagement science. 615 0$aAlgorithms. 615 0$aCombinatorics. 615 0$aComputer communication systems. 615 0$aMathematical optimization. 615 14$aOperations Research, Management Science. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aCombinatorics. 615 24$aComputer Communication Networks. 615 24$aOptimization. 676 $a511.5 700 $aDu$b Ding-Zhu$4aut$4http://id.loc.gov/vocabulary/relators/aut$061540 702 $aWan$b Peng-Jun$4aut$4http://id.loc.gov/vocabulary/relators/aut 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910437871803321 996 $aConnected Dominating Set: Theory and Applications$92539316 997 $aUNINA