Universität zu Köln

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:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
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:	Keywords Language WIRELESS NETWORKS; GRAPHS; ALGORITHMS; CLIQUES Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/47309