t-Spanners for metric space searching

The problem of Proximity Searching in Metric Spaces consists in finding the elements of a set which are close to a given query under some similarity criterion. In this paper we present a new methodology to solve this problem, which uses a t-spanner G′(V, E) as the representation of the metric database. A t-spanner is a subgraph G′(V, E) of a graph G(V, A), such that E  A and G′ approximates the shortest path costs over G within a precision factor t.

Our key idea is to regard the t-spanner as an approximation to the complete graph of distances among the objects, and to use it as a compact device to simulate the large matrix of distances required by successful search algorithms such as AESA. The t-spanner properties imply that we can use shortest paths over G′ to estimate any distance with bounded-error factor t.

For this sake, several t-spanner construction, updating, and search algorithms are proposed and experimentally evaluated. We show that our technique is competitive against current approaches. For example, in a metric space of documents our search time is only 9% over AESA, yet we need just 4% of its space requirement. Similar results are obtained in other metric spaces.

Finally, we conjecture that the essential metric space property to obtain good t-spanner performance is the existence of clusters of elements, and enough empirical evidence is given to support this claim. This property holds in most real-world metric spaces, so we expect that t-spanners will display good behavior in most practical applications. Furthermore, we show that t-spanners have a great potential for improvements.     

A limit characterization for the number of spanning trees of graphs

In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G_n} be a sequence of graphs G₀,G₁,G₂,… that belong to a particular class. We consider graphs of the form K_n−G_n that result from the complete graph K_n after removing a set of edges that span G_n. We study the spanning tree behaviour of the sequence {K_n−G_n} when n→∞ and the number of edges of G_n scales according to n. More specifically, we define the spanning tree indicator ({G_n}), a quantity that characterizes the spanning tree behaviour of {K_n−G_n}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.     

A family of network topologies with multiple loops and logarithmic diameter

A new family of network topologies containing multiple loops is discussed in this paper. In the proposed structure, N processors are interconnected to form a graph G(m, N), m 3, where m is a parameter of the graph such that N is an even multiple of m and (m − 1) × 2[(^{m− l)/2}]+ < N m × 2[^m/2]+1. The graph G(m, N) is hamiltonian with an average node degree (3 + l/m), when m is even and exactly 3 when m is odd. Whereas, the maximum node degree is 4. The diameter of G(m, N) is upper bounded by [11m/8]+ 1. A point to point routing algorithm has been presented. Implementation of ASCEND/DESCEND algorithms in O(m) time has been discussed. It has been shown that in case of a single node failure, the diameter increases by at most 6.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

On extended P4-reducible and extended P4-sparse graphs

A graph G was defined in [16] as P₄-reducible, if no vertex in G belongs to more than one chordless path on four vertices or P₄. A graph G is defined in [15] as P₄-sparse if no set of five vertices induces more than one P₄, in G. P₄-sparse graphs generalize both P₄-reducible and the well known class of p₄-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P₄-sparse and extended P₄-sparse graphs.

In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of P₄-sparse and a unique tree representation of P₄-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16–19]. The tree representation of an n-vertex P₄-sparse or a P₄-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP-complete on general graphs.

Finally, by relaxing the restriction concerning the exclusion of the C₅ cycles from P₄-sparse and P₄-reducible graphs, we introduce the class of the extended P4-sparse and the class of the extendedP₄-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs.     

Existence of multiple positive solutions for functional differential equations

In this paper, the existence of at least three positive solutions for the boundary value problem (BVP) of second-order functional differential equation with the form y″(t) + f(t, y^t) = 0, for t ε [0,1], y(t) -βy′(t) =η(t), for t ε [−τ,0], −γy(t) + Δy′(t) = ζ(t), for t ε [1, 1 + a], is studied. Moreover, we investigate the existence of at least three partially symmetric positive solutions for the above BVP with Δ = βγ.     

On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

In this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. A group of p agents or robots moving at unit speed searches for t. The search succeeds when an agent reaches the point t. Given a strategy S the competitive ratio is the ratio of the time needed by the agents to find t using S and the time needed if the location of t had been known in advance. We provide a strategy with competitive ratio of 1+2(m/p−1)(m/(m−p))^m/p and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case p = 1 is known in the literature as the cow path problem.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

On the k-path partition of graphs

The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs.     

New bounds for multi-label interval routing

Interval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2D for IR using one or more labels, and an upper bound of for IR using or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size for . This result implies a new upper bound of for IR using or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg [8] to achieve an upper bound of (1+)D for IR using O(n/D) or more labels, where is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme (M-IRS), where , we derive a lower bound of [(2M+1)/(2M)]D−1 on the longest path for , and a lower bound of [(2(1+δ)M+1)/(2(1+δ)M)]D, where δ(0,1], for . The latter result implies a lower bound of on the number of labels needed to achieve optimality.     

Efficient algorithms for shortest distance queries on special classes of polygons

The problem of finding a rectilinear minimum bend path (RMBP) between two designated points inside a rectilinear polygon has applications in robotics and motion planning. In this paper, we present efficient algorithms to solve the query version of the RMBP problem for special classes of rectilinear polygons given their visibility graphs. Specifically, we show that given an unweighted graph G = (V, E), with ¦V¦ = N and ¦E¦ = M, algorithms to preprocess G in linear space and time such that the shortest distance queries — queries asking for the distance between any pair of nodes in the graph — can be answered in constant time and space are presented in this paper. For the case of a chordal graph G, our algorithms give a distance which is at most one away from the actual shortest distance. When G is a K-chordal graph, our algorithm produces an exact shortest distance in O(K) time. We also present a non-trivial parallel implementation of the sequential preprocessing algorithm for the CREW-PRAM model which runs in O(log² N) time using O(N + M) processors. After the preprocessing, we can answer the queries in constant time using a single processor.     

New results on oscillation for delay differential equations with piecewise constant argument

We introduce a new technique to obtain some new oscillation criteria for the oscillating coefficients delay differential equation with piecewise constant argument of the form x′(t) + a(t)x(t) + b(t)x({t − k}) = 0, where a(t) and b(t) are right continuous functions on [−k, ∞), k is a positive integer, and [·] denotes the greatest integer function. Our results improve and generalize the known results in the literature. Some examples are also given to demonstrate the advantage of our results.     

Input constrained funnel control with applications to chemical reactor models

Error feedback control (in the presence of input constraints) is considered for a class of exothermic chemical reactor models. The primary control objective is regulation of a setpoint temperature T^* with prescribed accuracy: given λ>0 (arbitrarily small), ensure that, for every admissible system and reference setpoint, the regulation error e=T−T^* is ultimately smaller than λ (that is, ||e(t)||<λ for all t sufficiently large). The second objective is guaranteed transient performance: the evolution of the regulation error should be contained in a prescribed performance funnel F around the setpoint temperature T^*. A simple error feedback control with input constraints of the form

Full-size image

, u^* an offset, is introduced which achieves the objective in the presence of disturbances corrupting the measurement. The gain k(t) is a function of the error e(t)=T(t)−T^* and its distance to the funnel boundary. The input constraints have to satisfy certain feasibility assumptions in terms of the model data and the operating point T^*.     

Experimental numerical studies on a supercomputer of natural convection in an enclosure with localized heating

We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by −G/r^p + H/r^q.

In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time t_k = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations F_i,k = m_ia_i,k, I = 1, 2, 3, …, n, where m_i is the mass of the ith particle.

Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others.     

The monadic second-order logic of graphs V: on closing the gap between definability and recognizability

Context-free graph-grammars are considered such that, in every generated graph G, a derivation tree of G can be constructed by means of monadic second-order formulas that specify its nodes, its labels, the successors of a node etc. A subset of the set of graphs generated by such a grammar is recognizable iff it is definable in monadic second-order logic, whereas, in general, only the “if” direction holds.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

Collective Tree Spanners in Graphs with Bounded Parameters

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system $\mathcal{T}(G)In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system T(G)\mathcal{T}(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ? T(G)T\in\mathcal{T}(G) exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of O(?n)O(\sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree (2w)(2\mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree (2?c/2?w)(2\lfloor c/2\rfloor\mathsf{w}) -spanners and a system of 4log ₂ n collective additive tree (2(?c/3?+1)w)(2(\lfloor c/3\rfloor +1)\mathsf {w}) -spanners (here, w\mathsf{w} is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree (2w)(2\mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.     

Blended Hermite interpolants

In (Röschel, l997) B-spline technique was used for blending of Lagrange interpolants. In this paper we generalize this idea replacing Lagrange by Hermite interpolants. The generated subspline b(t) interpolates the Hermite input data consisting of parameter values t_i and corresponding derivatives a_i,j, j=0,…,_i−1, and is called blended Hermite interpolant (BHI). It has local control, is connected in affinely invariant way with the input and consists of integral (polynomial) segments of degree 2·k−1, where k−1max{_i}−1 denotes the degree of the B-spline basis functions used for the blending. This method automatically generates one of the possible interpolating subsplines of class C^k−1 with the advantage that no additional input data is necessary.