Schaudt, Oliver (2013). On dominating sets whose induced subgraphs have a bounded diameter. Discret Appl. Math., 161 (16-17). S. 2647 - 2653. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1872-6771
Full text not available from this repository.Abstract
We study dominating sets whose induced subgraphs have a bounded diameter. Such sets were used in recent papers by Kim et al. and Yu et al. to model virtual backbones in wireless networks where the number of hops required to forward messages within the backbone is minimized. We prove that for any fixed k >= 1 it is NP-complete to decide whether a given graph admits a dominating set whose induced subgraph has diameter at most k. On the upside, we give a characterization of the chordal graphs that admit such a dominating set. It turns out that in this characterization, the dominating set X can be chosen such that any shortest path between two members of the dominating set is entirely contained in X. Moreover, the characterization yields an O(mn) algorithm to compute, for a given connected chordal graph G on n vertices and m edges, the minimum k for which G has a dominating set whose induced subgraph has diameter at most k. Such a dominating set can be efficiently computed. (C) 2013 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||||||
Creators: |
|
||||||||
URN: | urn:nbn:de:hbz:38-473094 | ||||||||
DOI: | 10.1016/j.dam.2013.05.030 | ||||||||
Journal or Publication Title: | Discret Appl. Math. | ||||||||
Volume: | 161 | ||||||||
Number: | 16-17 | ||||||||
Page Range: | S. 2647 - 2653 | ||||||||
Date: | 2013 | ||||||||
Publisher: | ELSEVIER SCIENCE BV | ||||||||
Place of Publication: | AMSTERDAM | ||||||||
ISSN: | 1872-6771 | ||||||||
Language: | English | ||||||||
Faculty: | Unspecified | ||||||||
Divisions: | Unspecified | ||||||||
Subjects: | no entry | ||||||||
Uncontrolled Keywords: |
|
||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/47309 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |