A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks

Xiuzhen Cheng; Xiao Huang; Deying Li; Weili Wu; Ding-Zhu Du

doi:10.1002/net.10097

A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks

Xiuzhen Cheng, Xiao Huang, Deying Li, Weili Wu, Ding-Zhu Du

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

256 Citations (Scopus)

Abstract

A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum-connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum-connected dominating set in unit-disk graphs. In this paper, we design a (1 + 1/s)-approximation for the minimum-connected dominating set in unit-disk graphs, running in time n°((s log s)²). © 2003 Wiley Periodicals, Inc.

Original language	English
Pages (from-to)	202-208
Journal	Networks
Volume	42
Issue number	4
DOIs	https://doi.org/10.1002/net.10097
Publication status	Published - Dec 2003

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to <a href="mailto:[email protected]">[email protected]</a>.

Research Keywords

Connected dominating set
Partition
Polynomial-time approximation scheme
Unit disk graph

Access Output

10.1002/net.10097

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ba3e14cd0c5147609db8aac3f87d942f,

title = "A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks",

abstract = "A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum-connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum-connected dominating set in unit-disk graphs. In this paper, we design a (1 + 1/s)-approximation for the minimum-connected dominating set in unit-disk graphs, running in time n°((s log s)2). {\textcopyright} 2003 Wiley Periodicals, Inc.",

keywords = "Connected dominating set, Partition, Polynomial-time approximation scheme, Unit disk graph",

author = "Xiuzhen Cheng and Xiao Huang and Deying Li and Weili Wu and Ding-Zhu Du",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to <a href={"}mailto:[email protected]{"}>[email protected]</a>.",

year = "2003",

month = dec,

doi = "10.1002/net.10097",

language = "English",

volume = "42",

pages = "202--208",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks

AU - Cheng, Xiuzhen

AU - Huang, Xiao

AU - Li, Deying

AU - Wu, Weili

AU - Du, Ding-Zhu

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to <a href="mailto:[email protected]">[email protected]</a>.

PY - 2003/12

Y1 - 2003/12

N2 - A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum-connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum-connected dominating set in unit-disk graphs. In this paper, we design a (1 + 1/s)-approximation for the minimum-connected dominating set in unit-disk graphs, running in time n°((s log s)2). © 2003 Wiley Periodicals, Inc.

AB - A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum-connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum-connected dominating set in unit-disk graphs. In this paper, we design a (1 + 1/s)-approximation for the minimum-connected dominating set in unit-disk graphs, running in time n°((s log s)2). © 2003 Wiley Periodicals, Inc.

KW - Connected dominating set

KW - Partition

KW - Polynomial-time approximation scheme

KW - Unit disk graph

UR - http://www.scopus.com/inward/record.url?scp=2142846003&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-2142846003&origin=recordpage

U2 - 10.1002/net.10097

DO - 10.1002/net.10097

M3 - RGC 21 - Publication in refereed journal

SN - 0028-3045

VL - 42

SP - 202

EP - 208

JO - Networks

JF - Networks

IS - 4

ER -

A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks

Abstract

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this