Node-weighted Steiner tree approximation in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n ^O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.     

PTAS for minimum weighted connected vertex cover problem with <Emphasis Type="Italic">c</Emphasis>-local condition in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺, the minimum weighted connected vertex cover problem (MWCVC) is to seek a subset of vertices of the graph with minimum total weight, such that for any edge of the graph, at least one endpoint of the edge is contained in the subset, and the subgraph induced by this subset is connected. In this paper, we study the problem on unit disk graph. A polynomial-time approximation scheme (PTAS) for MWCVC is presented under the condition that the graph is c-local.     

A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

Polynomial time approximation schemes for minimum disk cover problems

The following planar minimum disk cover problem is considered in this paper: given a set D\mathcal{D} of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within a factor of (1+ε) in O(mn^{O(\frac1e2log2\frac1e)})\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})}) time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem are considered and approximation schemes are designed.     

A combinatorial theorem on labeling squares with points and its application

In this paper, we present a combinatorial theorem on labeling disjoint axis-parallel squares of edge length two using points. Given an arbitrary set of disjoint axis-parallel squares of edge length two, we show that if we label points on the boundary of all squares (one for each square) and define a distance label graph such that there is an edge between any two labeling points if and only if their L_∞-distance is at most 1 − ε (0 < ε < 1), then the maximum connected component of the graph contains Θ(1/ε) vertices, which is tight. With this theorem we present a new and simple factor-(3 + ε) approximation for labeling points with axis-parallel squares under the slider model. This research is supported by NSF CARGO Grant DMS-0138065.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Restricted domination parameters in graphs

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ _m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r _k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r _k (G,γ _m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r _k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r _k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Packing trees in communication networks

Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size. This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths. A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship for the fourth author.     

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.     

Restrained domination in cubic graphs

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then g_r(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then g_r(G) ￡ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ _r (G)=γ(G).     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

A PTAS for minimum weighted connected vertex cover $$P_3$$ problem in 3-dimensional wireless sensor networks

Given a connected and weighted graph \(G=(V, E)\) with each vertex v having a nonnegative weight w(v), the minimum weighted connected vertex cover \(P_{3}\) problem \((MWCVCP_{3})\) is required to find a subset C of vertices of the graph with minimum total weight, such that each path with length 2 has at least one vertex in C, and moreover, the induced subgraph G[C] is connected. This kind of problem has many applications concerning wireless sensor networks and ad hoc networks. When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. In this paper, we propose a new concept called weak c-local and give the first polynomial time approximation scheme (PTAS) for \(MWCVCP_{3}\) in unit ball graphs when the weight is smooth and weak c-local.     

Which trees have a differentiating-paired dominating set?

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. The set S is called a differentiating-paired dominating set if for every pair of distinct vertices u and v in V(G), N[u]∩S≠N[v]∩S, where N[u] denotes the set consisting of u and all vertices adjacent to u. In this paper, we provide a constructive characterization of trees that do not have a differentiating-paired dominating set.     

Total restrained domination in claw-free graphs

A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ _tr (G)=n. Also, we show that γ _tr (G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound.     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.     

Hardness and algorithms for rainbow connection

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In the first result of this paper we prove that computing rc(G) is NP-Hard solving an open problem from Caro et al. (Electron. J. Comb. 15, 2008, Paper R57). In fact, we prove that it is already NP-Complete to decide if rc(G)=2, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every ε>0, a connected graph with minimum degree at least ε n has bounded rainbow connection, where the bound depends only on ε, and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.     

Inapproximability and approximability of maximal tree routing and coloring

Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability of this problem and prove Ω(g^1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds. Supported in part by the NSF of China under Grant No. 70221001 and 60373012.     

On the power domination number of the generalized Petersen graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.     

Graphs with large paired-domination number

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that and we characterize the (infinite family of) graphs that achieve equality in this bound.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.