Search Results

In this paper we introduce a new, minimum-cuts based spanner algorithm, when the goal is twofold: (a) to decrease the number of active links in the network and (b) to maintain the ability of the SDN (Software-Defined Networking) controller to ...

Let G be a connected graph and $t\ge 1$ a (rational) constant. A t-spanner of G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. We address two problems on spanners. The first one, ...$_{}^{}$$_{}^{}$$_{}^{}$$_{}^{}$$\mathrm{}$$\mathrm{}$$_{}^{}$$\mathrm{}$$\mathrm{}$$\mathrm{}$$\mathrm{}$$_{\mathrm{}}^{}$$_{\mathrm{}}^{}$$_{\mathrm{}}^{}$$_{\mathrm{}}^{}$$_{\mathrm{}}^{}$

The greedy spanner in a low-dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades, as it possesses the two most basic properties of a good spanner: constant maximum degree and constant ...

We present a routing algorithm for the directed ${\mathrm{\Theta }}_4$-graph that computes a path between any two vertices s and t having length at most 17 times the Euclidean distance between s and t. To compute this path, at each step, the algorithm only uses ...${\mathrm{}}_{\mathrm{}}$$\sqrt{\mathrm{}}$

An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch $\sigma ⩾1$ is a data structure that preprocesses an input graph G. When queried with the triple (s, t, F), where $s,t\in V$ and $F\subseteq E$ contains at most f edges of G, the oracle returns an ...${\stackrel{}{}}_{}$${}_{}$$$${}_{}{\stackrel{}{}}_{}{}_{}$

For a constant t ≥ 1, a t-spanner of a connected graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. This concept, introduced by Peleg and Ullman in 1989, was ...

• Minimum t-spanner, for t ≥ 4, on planar graphs G with Δ(G) ≤ 4 is NP-hard.
• ...

• We study the Self-stabilizing dIrected t-Spanner for Autonomous nodes problem (SISA) in both 2D and 3D space.

Large-scale, self-organizing wireless ad hoc network deployments are being driven by recent developments of the Internet of Things (IoT) to collect information from a vast area or harsh environment efficiently. How to ensure fast ...

Topology control protocol aims at efficiently adjusting the network topology to improve the performance and scalability for networks, for example, spanner topology characteristics can decrease communication links and ensure that the distance of ...

Using the Well-Separated Pair Decomposition (WSPD) of Callahan and Kosaraju [JACM, 42(1):67–90, 1995], we present a construction of a $1+2/s+2/(s-1)$-spanner of size $O(s^{d}n)$ on a set of n points in ${\mathbf{R}}^d$ that we call a heavy-path WSPD-spanner, where $s>2$ ...$\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}$${}^{}$

We show that, unlike the Yao–Yao graph $Y{Y}_6$, the Theta–Theta graph $\Theta {\Theta }_6$ defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of points in non-convex position, the spanning ratio of $\Theta {\Theta }_6$ is unbounded.

In the problem of minimum connected dominating set with routing cost constraint, we are given a graph G = ( V , E ) and a positive integer α, and the goal is to find the smallest connected dominating set D of G such that, for any two ...

Let G=(V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch β if for every (u,v)źV V, distH(u,v)≤distG(u,v) + β. The problem of computing sparse spanners with small stretch ...

We establish an upper bound of 13 + 8 2 4.931 on the stretch factor of the Yao graph Y 4 defined in the L -metric, improving upon the best previously known upper bound of 6.31. We also establish an upper bound of ( 11 + 7 2 ) 4 + 2 2 54.62 on the ...

It is known that the problem of computing (Steiner) spanners on a set of n points has an ( n log n ) lower bound. However, the proof is based on an example of points on the real line. Therefore, if we assume that the points belong to the plane or higher ...

We study the spanning properties of Theta-Theta graphs. Similar in spirit with the Yao-Yao graphs, Theta-Theta graphs partition the space around each vertex into a set of cones, for some fixed integer , and select at most one edge per cone. The ...

Given a set of points in the plane, we show that the -graph with 5 cones is a geometric spanner with spanning ratio at most 50 + 22 5 9.960 . This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive ...

We study the problem of orienting a subset of edges of a given plane graph such that the resulting sub-digraph is strongly connected and spans all vertices of the graph. We are interested in orientations with minimum number of arcs which at the same ...

We compute BCP(s,t), a Best Coverage Path between two points s and t in the presence of m line segment obstacles in a 2D field under surveillance by n sensors. Based on nature of obstacles, we have studied two variants of the problem. For opaque ...

Let S be a set of n points in a metric space, let R={R"p:p@__ __S} be a set of positive real numbers, and let G"R be the undirected graph with vertex set S in which {p,q} is an edge if and only if |pq|= =1 is a constant, there always exists a set R such ...

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2k−1, 0)-spanner of size O(n^1+1/k) and an (...