06494nam 22008535 450 991043787180332120200630075539.01-4614-5242-210.1007/978-1-4614-5242-3(CKB)2670000000299665(EBL)1030657(OCoLC)819816599(SSID)ssj0000799483(PQKBManifestationID)11510633(PQKBTitleCode)TC0000799483(PQKBWorkID)10764057(PQKB)10295268(DE-He213)978-1-4614-5242-3(MiAaPQ)EBC1030657(MiAaPQ)EBC6312578(PPN)168302462(EXLCZ)99267000000029966520121026d2013 u| 0engur|n|---|||||txtccrConnected Dominating Set: Theory and Applications /by Ding-Zhu Du, Peng-Jun Wan1st ed. 2013.New York, NY :Springer New York :Imprint: Springer,2013.1 online resource (205 p.)Springer Optimization and Its Applications,1931-6828 ;77Description based upon print version of record.1-4899-8714-2 1-4614-5241-4 Includes bibliographical references (pages [193]-199) and index.Connected 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 Overview3.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 Coverage9.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; IndexThe 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.Springer Optimization and Its Applications,1931-6828 ;77Operations researchManagement scienceAlgorithmsCombinatoricsComputer communication systemsMathematical optimizationOperations Research, Management Sciencehttps://scigraph.springernature.com/ontologies/product-market-codes/M26024Algorithm Analysis and Problem Complexityhttps://scigraph.springernature.com/ontologies/product-market-codes/I16021Combinatoricshttps://scigraph.springernature.com/ontologies/product-market-codes/M29010Computer Communication Networkshttps://scigraph.springernature.com/ontologies/product-market-codes/I13022Optimizationhttps://scigraph.springernature.com/ontologies/product-market-codes/M26008Operations research.Management science.Algorithms.Combinatorics.Computer communication systems.Mathematical optimization.Operations Research, Management Science.Algorithm Analysis and Problem Complexity.Combinatorics.Computer Communication Networks.Optimization.511.5Du Ding-Zhuauthttp://id.loc.gov/vocabulary/relators/aut61540Wan Peng-Junauthttp://id.loc.gov/vocabulary/relators/autMiAaPQMiAaPQMiAaPQBOOK9910437871803321Connected Dominating Set: Theory and Applications2539316UNINA