Search

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2.⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k-1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2.⌈k/2⌉ (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is A P X-hard. [ABSTRACT FROM AUTHOR]

We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form 'Are vertices u and v connected with a path?" in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in a total of O( n) time. This results improves over a previously known O( n log n) time algorithm. [ABSTRACT FROM AUTHOR]

Let G( V, E) be a connected and undirected graph with n-vertex-set V and m-edge-set E. For each v ∈ V, let N( v) = { u| v ∈ V and( u, v) ∈ E}. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V( G) to a k-bit Boolean string f( v) = f ( v) f ( v) ... f ( v), i.e., f ( v) ∈ {0, 1}, 1 ≤ i ≤ k, such that for any vertex v with f( v) = 0 we have ⋈ f( u) = 1, for all v ∈ V, where ⋈ f( u) denotes the result of taking bitwise OR operation on f( u), for all u ∈ S. The weight of f is defined as $w(f) = {\sum }_{v\in V}{\sum }^{k}_{i=1} f_{i}(v)$ . The k-rainbow domination number γ ( G) is the minimum weight of a k-rainbow dominating function over all k-rainbow dominating functions of G. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G. In this paper, we determine γ ( S( n, m)), γ ( S ( n, m)), and γ ( S ( n, m)), where S( n, m), S ( n, m), and S ( n, m) are Sierpiński graphs and extended Sierpiński graphs. [ABSTRACT FROM AUTHOR]

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one lightpath. The placement of regenerators has become an active area of research during recent years, and various optimization problems have been studied. The first such problem is the Regeneration Location Problem (Rlp), where the goal is to place the regenerators so as to minimize the total number of nodes containing them. We consider two extreme cases of online Rlp regarding the value of d and the number k of regenerators that can be used in any single node. (1) d is arbitrary and k unbounded. In this case a feasible solution always exists. We show an O(log| X|⋅ log d)-competitive randomized algorithm for any network topology, where X is the set of paths of length d. The algorithm can be made deterministic in some cases. We show a deterministic lower bound of ${\Omega } \left (\frac {\log (|{E}|/d) \cdot \log d}{\log (\log (|{E}|/d) \cdot \log d)}\right )$ , where E is the edge set. (2) d = 2 and k = 1. In this case there is not necessarily a solution for a given input. We distinguish between feasible inputs (for which there is a solution) and infeasible ones. In the latter case, the objective is to satisfy the maximum number of lightpaths. For a path topology we show a lower bound of $\sqrt {l}/2$ for the competitive ratio (where l is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs. [ABSTRACT FROM AUTHOR]

We consider the Geometric Connected Facility Location Problem (GCFLP): given a set of clients $\mathcal {C} \subset \mathbb {R}^{d}$ , one wants to select a set of locations $F \subset \mathbb {R}^{d}$ where to open facilities, each at a fixed cost f≥0. For each client $j \in \mathcal {C}$ , one has to choose to either connect it to an open facility ϕ( j)∈ F paying the Euclidean distance between j and ϕ( j), or pay a given penalty cost π( j). The facilities must also be connected by a tree T, whose cost is M ℓ( T), where M≥1 and ℓ( T) is the total Euclidean length of edges in T. The multiplication by M reflects the fact that interconnecting two facilities is typically more expensive than connecting a client to a facility. The objective is to find a solution with minimum cost. In this paper, we present a Polynomial-Time Approximation Scheme (PTAS) for the two-dimensional GCFLP. Our algorithm also leads to a PTAS for the two-dimensional Geometric Connected k-medians, when f=0, but only k facilities may be opened. [ABSTRACT FROM AUTHOR]

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a ( u, v)-journey for any pair of vertices u, v, u ≠ v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = N P. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlog n labels. [ABSTRACT FROM AUTHOR]