Skip to main content
SpringerLink
Log in
Book cover

Connected Dominating Set: Theory and Applications

  • Textbook
  • © 2013

Overview

Authors:
  1. Ding-Zhu Du

    1. , Department of Computer Science, University of Texas, Dallas, Richardson, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Peng-Jun Wan

    1. , Department of Computer Science, Illinois Institute of Technology, Chicago, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • 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)

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

Access this book

Log in via an institution
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

Licence this eBook for your library

Institutional subscriptions

Table of contents (12 chapters)

  1. Front Matter

    Pages i-ix
    Download chapter PDF

  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
    Download chapter PDF
Back to top

Keywords

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

Publish with us

Policies and ethics

Back to top

Search

Navigation