The Resource Connected Dominating Set: Theory and Applications, by Ding-Zhu Du, Peng-Jun Wan, (electronic resource)

Connected Dominating Set: Theory and Applications, by Ding-Zhu Du, Peng-Jun Wan, (electronic resource)

Label
Connected Dominating Set: Theory and Applications
Title
Connected Dominating Set: Theory and Applications
Statement of responsibility
by Ding-Zhu Du, Peng-Jun Wan
Creator
Contributor
Author
Author
Subject
Language
  • eng
  • eng
Summary
The 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
Member of
http://library.link/vocab/creatorName
Du, Ding-Zhu
Dewey number
511.34
http://bibfra.me/vocab/relation/httpidlocgovvocabularyrelatorsaut
  • 1Bq-0Wab-OY
  • 22JBRKqcRTI
Language note
English
LC call number
  • QA402-402.37
  • T57.6-57.97
Literary form
non fiction
Nature of contents
dictionaries
http://library.link/vocab/relatedWorkOrContributorName
Wan, Peng-Jun.
Series statement
Springer Optimization and Its Applications,
Series volume
77
http://library.link/vocab/subjectName
  • Computer software
  • Combinatorics
  • Computer Communication Networks
  • Mathematical optimization
  • Operations Research, Management Science
  • Algorithm Analysis and Problem Complexity
  • Combinatorics
  • Computer Communication Networks
  • Optimization
Label
Connected Dominating Set: Theory and Applications, by Ding-Zhu Du, Peng-Jun Wan, (electronic resource)
Instantiates
Publication
Note
Description based upon print version of record
Carrier category
online resource
Carrier category code
  • cr
Content category
text
Content type code
  • txt
Contents
  • 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 Overview
  • 3.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
  • 9.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
Dimensions
unknown
Edition
1st ed. 2013.
Extent
1 online resource (205 p.)
Form of item
online
Isbn
9781461452423
Media category
computer
Media type code
  • c
Other control number
10.1007/978-1-4614-5242-3
Specific material designation
remote
System control number
  • (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
  • (EXLCZ)992670000000299665
Label
Connected Dominating Set: Theory and Applications, by Ding-Zhu Du, Peng-Jun Wan, (electronic resource)
Publication
Note
Description based upon print version of record
Carrier category
online resource
Carrier category code
  • cr
Content category
text
Content type code
  • txt
Contents
  • 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 Overview
  • 3.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
  • 9.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
Dimensions
unknown
Edition
1st ed. 2013.
Extent
1 online resource (205 p.)
Form of item
online
Isbn
9781461452423
Media category
computer
Media type code
  • c
Other control number
10.1007/978-1-4614-5242-3
Specific material designation
remote
System control number
  • (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
  • (EXLCZ)992670000000299665

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...