Blossoms are polar forms

Consider the functions H(t):=t² and h(u,v):=uv. The identity H(t)=h(t,t) shows that h is the restriction of h to the diagonal u=v in the uv-plane. Yet, in many ways, a bilinear function like h is simpler than a homogeneous quadratic function like H. More generally, if F(t) is some n-ic polynomial function, it is often helpful to study the polar form of F, which is the unique symmetric, multiaffine function ƒ(u_1,…u_n) satisfying the identity F(t)=f(t,…,t). The mathematical theory underlying splines is one area where polar forms can be particularly helpful, because two pieces F and G of an n-ic spline meet at a point r with C^k parametric continuity if and only if their polar forms ƒ and g agree on all sequences of n arguments that contain at least n-k copies of r.

The polar approach to the theory of splines emerged in rather different guises in three independent research efforts: Paul de Faget Casteljau called it ‘shapes through poles’; Carl de Boor called it ‘B-splines without divided differences’; and Lyle Ramshaw called it ‘blossoming’. This paper reviews the work of de Casteljau, de Boor, and Ramshaw in an attempt to clarify the basic principles that underly the polar approach. It also proposes a consistent system of nomenclature as a possible standard.     

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.     

Computational complexity of distributed detection problems with information constraints

For a system consisting of a set of sensors S = {S₁, S₂, …, S_m} and a set of objects O = {O₁, O₂, …, O_n}, there are information constraints given by a relation R S × O such that (S_i, O_j) R if and only if S_i is capable of detecting O_j. Each (S_i, O_j) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (S_i, O_j) R, for all S_i S, O_j O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.     

Properties of Noncentral Dirichlet Distributions

Let X₁,…, X_r+1 be independent random variables, X_iGa (a_i, θ, δ_i), i = 1,…, r + 1. Define and V_i = X_i/X_r+1, i = 1,…, r. Then, (U₁,…, U_r) and (V₁,…, V_r) follow noncentral Dirichlet Type 1 and Type 2 distributions, respectively. In this article several properties of these distributions and their connections with the uniform, the noncentral multivariate-F and the noncentral multivariate-t distributions are discussed.     

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.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

Paired-domination in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique K_d. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ_p(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)2, then n(G)γ_p(G_I)4m(G)/[δ(G)+1], and the equality γ_p(G_I) = n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.     

Simultaneous H control of a finite collection of linear plants with a single nonlinear digital controller

This paper considers the problem of simultaneous H^∞ control of a finite collection of linear time-invariant systems via a nonlinear digital output feedback controller. The main result is given in terms of the existence of suitable solutions to Riccati algebraic equations and a dynamic programming equation. Our main result shows that if the simultaneous H^∞ control problem for k linear time-invariant plants of orders n₁,n₂,…,n_k can be solved, then this problem can be solved via a nonlinear time-invariant controller of order nn₁+n₂++n_k.     

A new routing algorithm for multirate rearrangeable Clos networks

In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the “grouping algorithm”. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that m = 2n+(n−1)/2^k is a sufficient number of middle-stage switches for the symmetric three-stage Clos network C(n,m,r) to be multirate rearrangeable, where k is any positive integer and rn/(2^k−1).     

A new way of counting n

In this paper, we shall give a combinatorial proof of the following equation:

,

where m and n are positive integers, m ≤ n, and k₁, k₂, …, k_n-1 are nonnegative integers.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.     

1-Inverses for polynomial matrices of non-constant rank

Let p₁, … p_t be polynomials in ⁿ with a variety V of common zeros contained in a suitable open set U. Explicit formulas are provided to construct rational functions λ₁, … λ_s such that Σ_i=1^sp_iλ_i 1, and such that the singularities of the λ_i are contained in U. This result is applied to compute rational functions-valued 1-inverses of matrices with polynomial coefficients, which do not have constant rank, while retaining control over the location of the singularities of the rational functions themselves.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

A fast algorithm for parametric curve plotting

In parametric curve plotting by means of line segments, a curve r = r(t), t[t₀, t_u] is given, and a set of ordered points r(t_i, iN, t_ie[t₀, t_u] is specified as the vertices of an inscribed polygon of the curve. There are several, analytical, numerical or intuitive ways to derive these vertices obtaining a smooth polygonal approximation. The methods, which can be found in the literature, either belong to some special curves or involve a considerable waste of computing time.

In this paper, we consider an algorithm that appears as a subroutine in the whole program. The subroutine allows the main program to space points as a function of a distance interval for any parametric curve. The design of the routine for performing this spacing is outlined and two examples are shown.     

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).     

Sojourn time distribution in the M/M/1 queue with discriminatory processor-sharing

In this paper, we consider a queue with multiple K job classes, Poisson arrivals, exponentially distributed required service times in which a single processor serves according to the DPS discipline. More precisely, if there are n_i class i jobs in the system, i=1,…,K, each class j job receives a fraction _j/∑_i=1^K_in_i of the processor capacity. For this queue, we obtain a system of equations for joint transforms of the sojourn time and the number of jobs. Using this system of equations we find the moments of the sojourn time as a solution of linear simultaneous equations, which solves an open problem.     

The role of coherence in eliciting and handling imprecise probabilities and its application to medical diagnosis

We refer to an arbitrary family of events (hypotheses), i.e., has neither any particular algebraic structure nor is a partition of the certain event Ω. We detect logical relations among the given events (the latter could represent some possible diseases), and some further information is carried by probability assessments, relative to an event E (e.g., a symptom) conditionally to some of the H_i's (“partial likelihood”). If we assess (prior) probabilities for the events H_i's, then the ensuing problems are: (i) is this assessment coherent? (ii) is the partial likelihood coherent “per se”? (iii) is the global assignment (the initial one together with the likelihood) coherent? If the relevant answers are all YES, then we may try to “update” (coherently) the priors P(H_i) into the posteriors P(H_i|E). This is an instance of a more general issue, the problem of coherent extensions: a very particular case is Bayes' updating for exhaustive and mutually exclusive hypotheses, in which this extension is unique. In the general case the lack of uniqueness gives rise to upper and lower updated probabilities, and we could now update again the latter, given a new event F and a corresponding (possibly partial) likelihood. In this paper, many relevant features of this problem are discussed, keeping an eye on the distinction between semantic and syntactic aspects.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

On the error in Padé approximations for functions defined by Stieltjes integrals

Consdier I(z) = ∫^b_a w(t)f(t, z) dt, f(t, z) = (1 + t/z)⁻¹. It is known that generalized Gaussian quadrature of I(z) leads to approximations which occupy the (n, n + r − 1) positions of the Padé matrix table for I(z). Here r is a positive integer or zero. In a previous paper the author developed a series representation for the error in Gaussian quadrature. This approach is now used to study the error in the Padé approximations noted. Three important examples are treated. Two of the examples are generalized to the case where f(t, z) = (1 + t/z)^−v.