Skip to main content
  • Textbook
  • © 2013

Connected Dominating Set: Theory and Applications

  • This unique book may be used as a reference and/or supplementary text in a graduate seminar
  • The expository content and complete list of references in each chapter bring the reader quickly to the forefront of research
  • Wide applications of connected dominating sets attract readers not only from optimization and theoretical computer science, but also from computer communication networks and industrial engineering

Part of the book series: Springer Optimization and Its Applications (SOIA, volume 77)

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 54.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (12 chapters)

  1. Front Matter

    Pages i-ix
  2. Introduction

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 1-9
  3. CDS in General Graph

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 11-34
  4. CDS in Unit Disk Graph

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 35-62
  5. CDS in Unit Ball Graphs and Growth Bounded Graphs

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 63-75
  6. Weighted CDS in Unit Disk Graph

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 77-104
  7. Coverage

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 105-118
  8. Routing-Cost Constrained CDS

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 119-131
  9. CDS in Disk-Containment Graphs

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 133-149
  10. CDS in Disk-Intersection Graphs

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 151-159
  11. Geometric Hitting Set and Disk Cover

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 161-167
  12. Minimum-Latency Scheduling

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 169-182
  13. CDS in Planar Graphs

    • Ding-Zhu Du, Peng-Jun Wan
    Pages 183-191
  14. Back Matter

    Pages 193-203

About this book

The connected dominating set has been a classic subject studied in graph theory since 1975. Since the 1990s, it has been found to have 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. In this book, we are going to collect recent developments on the connected dominating set, which presents the state of the art in the study of connected dominating sets. The book consists of 16 chapters. Except the 1st one, each chapter is devoted to one problem, and consists of three parts, motivation and overview, problem complexity analysis, and approximation algorithm designs, which will lead the reader to see clearly about the background, formulation, existing important research results, and open problems. Therefore, this would be a very valuable reference book for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, and discrete mathematics.

Authors and Affiliations

  • , Department of Computer Science, University of Texas, Dallas, Richardson, USA

    Ding-Zhu Du

  • , Department of Computer Science, Illinois Institute of Technology, Chicago, USA

    Peng-Jun Wan

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 54.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access