Minimum power strongly connected dominating sets in wireless networks

Deying Li; Hongwei Du; Pengjun Wan; Xiaofeng Gao; Zhao Zhang; Weili Wu

Minimum power strongly connected dominating sets in wireless networks

Deying Li, Hongwei Du, Pengjun Wan, Xiaofeng Gao, Zhao Zhang, Weili Wu

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

4 Citations (Scopus)

Abstract

Consider a digraph G = (V, E). A subset of vertices D⊆Vis called a strongly connected dominating set if the subgraph induced by D is strongly connected and every vertex not in D is incident to an in-edge coming from D and also to an out-edge going to D. Strongly connected dominating set is a virtual backbone in ad-hoc wireless networks. It should be kept active all the time. Therefore, constructing an energy-efficient strongly connected dominating set is significant. Since this problem is NP-hard, in this paper we give an O(ln n )-approximation for the minimum power strongly connected dominating set, which is the weighted version where each node has been assigned a power function.

Original language	English
Title of host publication	Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008
Pages	447-451
Publication status	Published - 2008
Event	2008 International Conference on Wireless Networks, ICWN 2008 - Las Vegas, NV, United States Duration: 14 Jul 2008 → 17 Jul 2008

Publication series

Name	Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008

Conference

Conference	2008 International Conference on Wireless Networks, ICWN 2008
Place	United States
City	Las Vegas, NV
Period	14/07/08 → 17/07/08

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 [email protected].

Funding

§Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA. Support in part by National Science Foundation under grants CCF-9208913 and CCF-0728851. ¶Corresponding author. Tel: 214-554-4518. kDepartment of Mathematics, Xingjiang University, Urmuqi, China. Support in part by NSFC (60603003) and XJEDU. This work was done while this author visited at University of Texas at Dallas.

Research Keywords

Connected dominating set
Energy efficient
Wireless network

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{a535c330623743fea49dcbb90c5244f8,

title = "Minimum power strongly connected dominating sets in wireless networks",

abstract = "Consider a digraph G = (V, E). A subset of vertices D⊆Vis called a strongly connected dominating set if the subgraph induced by D is strongly connected and every vertex not in D is incident to an in-edge coming from D and also to an out-edge going to D. Strongly connected dominating set is a virtual backbone in ad-hoc wireless networks. It should be kept active all the time. Therefore, constructing an energy-efficient strongly connected dominating set is significant. Since this problem is NP-hard, in this paper we give an O(ln n )-approximation for the minimum power strongly connected dominating set, which is the weighted version where each node has been assigned a power function.",

keywords = "Connected dominating set, Energy efficient, Wireless network",

author = "Deying Li and Hongwei Du and Pengjun Wan and Xiaofeng Gao and Zhao Zhang and Weili Wu",

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 [email protected].; 2008 International Conference on Wireless Networks, ICWN 2008 ; Conference date: 14-07-2008 Through 17-07-2008",

year = "2008",

language = "English",

isbn = "1601320914",

series = "Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008",

pages = "447--451",

booktitle = "Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008",

}

Li, D, Du, H, Wan, P, Gao, X, Zhang, Z & Wu, W 2008, Minimum power strongly connected dominating sets in wireless networks. in Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008. Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008, pp. 447-451, 2008 International Conference on Wireless Networks, ICWN 2008, Las Vegas, NV, United States, 14/07/08.

Minimum power strongly connected dominating sets in wireless networks. / Li, Deying; Du, Hongwei; Wan, Pengjun et al.
Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008. 2008. p. 447-451 (Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Minimum power strongly connected dominating sets in wireless networks

AU - Li, Deying

AU - Du, Hongwei

AU - Wan, Pengjun

AU - Gao, Xiaofeng

AU - Zhang, Zhao

AU - Wu, Weili

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 [email protected].

PY - 2008

Y1 - 2008

N2 - Consider a digraph G = (V, E). A subset of vertices D⊆Vis called a strongly connected dominating set if the subgraph induced by D is strongly connected and every vertex not in D is incident to an in-edge coming from D and also to an out-edge going to D. Strongly connected dominating set is a virtual backbone in ad-hoc wireless networks. It should be kept active all the time. Therefore, constructing an energy-efficient strongly connected dominating set is significant. Since this problem is NP-hard, in this paper we give an O(ln n )-approximation for the minimum power strongly connected dominating set, which is the weighted version where each node has been assigned a power function.

AB - Consider a digraph G = (V, E). A subset of vertices D⊆Vis called a strongly connected dominating set if the subgraph induced by D is strongly connected and every vertex not in D is incident to an in-edge coming from D and also to an out-edge going to D. Strongly connected dominating set is a virtual backbone in ad-hoc wireless networks. It should be kept active all the time. Therefore, constructing an energy-efficient strongly connected dominating set is significant. Since this problem is NP-hard, in this paper we give an O(ln n )-approximation for the minimum power strongly connected dominating set, which is the weighted version where each node has been assigned a power function.

KW - Connected dominating set

KW - Energy efficient

KW - Wireless network

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

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

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 1601320914

SN - 9781601320919

T3 - Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008

SP - 447

EP - 451

BT - Proceedings of the 2008 International Conference on Wireless Networks, ICWN 2008

T2 - 2008 International Conference on Wireless Networks, ICWN 2008

Y2 - 14 July 2008 through 17 July 2008

ER -

Minimum power strongly connected dominating sets in wireless networks

Abstract

Publication series

Conference

Bibliographical note

Funding

Research Keywords

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this