A Survey on Investigating the Need for Intelligent Power-Aware Load Balanced Routing Protocols for Handling Critical Links in MANETs <s> 8 <s> The problem of determining the minimum number gamma of edges to be added to a graph G so that in the resulting graph the edge-connectivity between every pair (u,v) of nodes is at least a prescribed value r(u,v) is treated. A min-max formula for gamma is derived, and a polynomial-time algorithm for computing gamma is described. The directed counterpart of the problem is also solved for the case in which r(u,v)=k>or=1. The approach used makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge costs arise from node costs. > <s> BIB001 </s> A Survey on Investigating the Need for Intelligent Power-Aware Load Balanced Routing Protocols for Handling Critical Links in MANETs <s> 8 <s> In the survivable network design problem SNDP, the goal is to find a minimum-cost subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertexdisjoint paths connecting them.We give the first lower bound on the approximability of SNDP, showing that the problem admits no efficient 2log1-?n ratio approximation for any fixed ? > 0 unless NP ? DTIME(npolylog(n)>). We also show hardness of approximation results for several important special cases of SNDP, including constant factor hardness for the k-vertex connected spanning subgraph problem (k-VCSS) and for the vertex-connectivity augmentation problem, even when the edge costs are severely restricted. <s> BIB002 </s> A Survey on Investigating the Need for Intelligent Power-Aware Load Balanced Routing Protocols for Handling Critical Links in MANETs <s> 8 <s> Given a graph G = (V,E) and an integer D > 1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP. For a forest G and an odd D > 3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D; our algorithm delivers an 8-approximate solution in O(|V| 3 ) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if an augmented graph is additionally required to be biconnected. <s> BIB003 </s> A Survey on Investigating the Need for Intelligent Power-Aware Load Balanced Routing Protocols for Handling Critical Links in MANETs <s> 8 <s> Given an undirected multigraph G = (V, E), a family W of sets W ⊆ V of vertices (areas), and a requirement function r : W → Z+ (where Z+ is the set of nonnegative integers) we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v ∈ V and an area W ∈ W. So far this problem was shown to be NP-hard in the uniform case of r(W) = 1 for each W ∈ W, and polynomially solvable in the uniform case of r(W) = r ≥ 2 for each W ∈ W. In this paper, we show that the problem can be solved in O(m + pn4(r* + logn)) time, even if r(W) ≥ 2 holds for each W ∈ W, where n = |V|, m = |{{u, v}|(u, v) ∈ E}|, p = |W|, and r* = max{r(W)|W ∈ W}. <s> BIB004 </s> A Survey on Investigating the Need for Intelligent Power-Aware Load Balanced Routing Protocols for Handling Critical Links in MANETs <s> 8 <s> When a link or node failure occurs, flows are detoured around the failed portion, so the hop count of flows could change dramatically as a result of a failure. It is therefore important to evaluate the reliability of backbone networks from the viewpoint of flow hop length stability as well as network connectivity. In this paper, we analyze the possible primary causes of the degradation of reliability of the backbone networks of 36 commercial ISPs and present guidelines for making effective investments in link addition. <s> BIB005 </s> A Survey on Investigating the Need for Intelligent Power-Aware Load Balanced Routing Protocols for Handling Critical Links in MANETs <s> 8 <s> When a link or node failure occurs in a network, flows are detoured and therefore the hop counts of the flows increase. This increase could drastically deteriorate the quality of a network. The flow hop length stability as well as network connectivity is important for network reliability. We investigate a network design method that improves stability and connectivity of a network during a failure with a limited investment cost. We formalize a network design problem, prove that this problem is NP-complete, and propose an approximation algorithm. In addition, we evaluate the performance of the algorithm by using publicly available data for 39 backbone networks of commercial ISPs and networks generated by two well-known models. The results show that the proposed algorithm provides effective solutions from a practical viewpoint in sufficiently small computation time. <s> BIB006
The Scientific World Journal this grouping has to be very dynamic in nature for efficient reduction of communication overhead. In the literature, there exist many network design methods to enhance the reliability and the performance by adding links to an existing network. There is a problem for determining a set of edges to meet the required edge connectivity or vertex connectivity by adding edges to a graph BIB001 BIB002 BIB004 . For considering path length, there is a problem for determining a set of edges to meet the required diameter by adding edges to a graph  BIB003  . Chordal graph completion problem, interval graph completion problem, and Hamilton graph completion problem determine a set of added edges to make a given graph, a chordal graph, an interval graph, and a Hamilton graph, respectively  . Kamiyama and Miwa BIB005 deal with the measure to evaluate both the reliability and the performance and Katayama et al. BIB006 proposed an approximation algorithm for a problem to enhance both the reliability and the performance based on the measure by adding links to an existing network.