Routing-efficient CDS construction in Disk-Containment Graphs
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lu, Zaixin | - |
dc.contributor.author | Wu, Lidong | - |
dc.contributor.author | Pardalos, Panos M. | - |
dc.contributor.author | Maslov, Eugene | - |
dc.contributor.author | Lee, Wonjun | - |
dc.contributor.author | Du, Ding-Zhu | - |
dc.date.accessioned | 2021-09-05T11:32:17Z | - |
dc.date.available | 2021-09-05T11:32:17Z | - |
dc.date.created | 2021-06-15 | - |
dc.date.issued | 2014-02 | - |
dc.identifier.issn | 1862-4472 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/99333 | - |
dc.description.abstract | In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | SPRINGER HEIDELBERG | - |
dc.subject | CONNECTED DOMINATING SETS | - |
dc.subject | WIRELESS NETWORKS | - |
dc.subject | APPROXIMATION ALGORITHMS | - |
dc.subject | VIRTUAL BACKBONE | - |
dc.subject | RANGES | - |
dc.title | Routing-efficient CDS construction in Disk-Containment Graphs | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Lee, Wonjun | - |
dc.identifier.doi | 10.1007/s11590-012-0590-5 | - |
dc.identifier.scopusid | 2-s2.0-84893753844 | - |
dc.identifier.wosid | 000330949700003 | - |
dc.identifier.bibliographicCitation | OPTIMIZATION LETTERS, v.8, no.2, pp.425 - 434 | - |
dc.relation.isPartOf | OPTIMIZATION LETTERS | - |
dc.citation.title | OPTIMIZATION LETTERS | - |
dc.citation.volume | 8 | - |
dc.citation.number | 2 | - |
dc.citation.startPage | 425 | - |
dc.citation.endPage | 434 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Operations Research & Management Science | - |
dc.relation.journalResearchArea | Mathematics | - |
dc.relation.journalWebOfScienceCategory | Operations Research & Management Science | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.subject.keywordPlus | CONNECTED DOMINATING SETS | - |
dc.subject.keywordPlus | WIRELESS NETWORKS | - |
dc.subject.keywordPlus | APPROXIMATION ALGORITHMS | - |
dc.subject.keywordPlus | VIRTUAL BACKBONE | - |
dc.subject.keywordPlus | RANGES | - |
dc.subject.keywordAuthor | Wireless network | - |
dc.subject.keywordAuthor | CDS | - |
dc.subject.keywordAuthor | Routing efficiency | - |
dc.subject.keywordAuthor | Approximation algorithm | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.