A refined search tree technique for Dominating Set on planar graphs

Title: A refined search tree technique for Dominating Set on planar graphs
Creator: Alber, Jochen; Fan, Hongbing; Fellows, Michael R.; Fernau, Henning; Niedermeier, Rolf; Rosamond, Fran; Stege, Ulrike
Relation: Journal of Computer and System Sciences Vol. 71, no. 4, p. 385-405
Publisher: Academic Press
Resource Type: journal article
Date: 2005
Description: We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8kn) and O(8kk+n3), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general "annotated" problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.
Identifier: http://hdl.handle.net/1959.13/24506
Identifier: uon:86
Identifier: ISSN:1090-2724
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format