Mathematics – Combinatorics
Scientific paper
2011-10-24
Mathematics
Combinatorics
10 pages, 0 figures
Scientific paper
The k-domination number of a graph is the minimum size of a set X such that every vertex of G is in distance at most k from X. We give a linear time constant-factor approximation algorithm for k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, classes closed on topological minors or classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge. The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each pair of vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that |D|=O(|A|), and these sets can be found in linear time. For domination number (k=1) the assumptions can be relaxed, and the result holds for all graph classes with arrangeability bounded by a constant.
No associations
LandOfFree
Constant-factor approximation of domination number in sparse graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constant-factor approximation of domination number in sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constant-factor approximation of domination number in sparse graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-520324