TITLE: Small k-Dominating Sets in Planar Graphs with Applications
AUTHORS: Cyril Gavoille, David Peleg, André Raspaud and Eric Sopena
ABSTRACT:
A subset of nodes S in a graph G is called
k-dominating if, for every node u of the graph,
the distance from u to S is at most k. We
consider the parameter \gammak(G) defined as
the cardinality of the smallest k-dominating set of G.
For planar graphs, we show that for every e>0 and for every
k>=(5/7+e)D, \gammak(G)
= O(1/e). For several subclasses of planar graphs of diameter
D, we show that \gammak(G) is bounded
by a constant for k>=D/2. We conjecture that the same
result holds for every planar graph. This problem is motivated by the
design of routing schemes with compact data structures.