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.     

A simple solution to the l optimization problem

It is pointed out in this brief paper that the l¹ optimization problem min_{Q ε lqp¹} | H − U * Q * V |₁, H ε l_mn¹, U ε l_mq¹, V ε l_pn¹ can be solved in one step rather than two. The solution of the dual problem is obviated by the direct solution of the primal problem via linear programming. The method here is applicable to finite-dimensional problems or approximating finite-dimensional problems, in the general case.     

On the latent roots of λ matrices

In this paper we consider equations defined by (1.3)–(1.2)–(1.4). We describe in detail three algorithms for the approximate determination of |λ_nr|, for |λ₁| resp. for one of the λ_j's. The single steps of the algorithms are the four fundamental operations and the positive value of k^th roots of positive numbers and the main interest of them lies in the fact that (the algorithms themselves and so) their lengths depend only on n, r and the prescribed relative error and not on the entries of the matrices A_ν.     

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.     

A linear time algorithm for maximum matchings in convex, bipartite graphs

The problem of determining the maximum matching in a convex bipartite graph, G = (V₁, V₂, E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(|V₁|) time.     

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.     

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.     

Minimizing the distance to one evader while chasing another

To approach a simple game Δ² of P and E = {E₁, E₂} with no a priori evaders' role assignment and the payoff equal to the distance to one evader at an instant of catching another, we introduce a concept of casting and study the games Δ_1,2 and Δ_2,1 for preassigned and Δ_p² for open-loop casting procedures. Since Δ_p² is reduced to Δ_1,2 or Δ_2,1 which, in turn, are distinguished only by their notations, we focus attention mainly on Δ_1,2. According to the tenet of transition, Δ_1,2 is divided into a concatenation of Δ_1,2^b (basic) and Δ_1,2^a (auxiliary) games that model the problem before and after the first instant of E₁ capture. The games Δ_1,2^a, Δ_1,2^b, Δ_1,2 are studied one after another with use of the Isaacs' approach extended by Berkowitz, Breakwell, Bernhard et al.     

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.     

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.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.     

Thermodynamics of the cao-si02 system

In order to maintain consistency, analytical expressions for the free energy of mixing of phases should reproduce not only the phase diagrams but also the experimentally determined activities. Information on the partial molar free energies and the phase boundaries, in turn, can be used to estimate the free energy of formation of compounds.

An examination of thermochemical data in the CaO-SiO₂ system showed that ΔGδf values for -Ca₂Si0₄, which are stable at temperatures above 1710°K, are limited a maximum of 1800°K. The free energy of formation in a temperature range from about 1700 to 2400°K was estimated from the phase boundary and the activity of silica to be as follows:

2Ca0(s) + Si0₂(cristo.) = Ca2Si0₄() ΔG°f = −86303.50 − 34.338 Tjoules

An analytical expression for the free energy of mixing of the liquid phase was obtained for the entire composition range in the CaO-Si0₂ system. Confidence in the estimated G‡f for -Ca₂Si0₄ was demonstrated by good agreement of the calculated phase diagram and the experimentally determined activity of silica.     

Behavior of the beta-splines with values of the parameters beta2 negative

In this paper we study the behavior of the beta-spline functions in the case the parameter β₂(i) is negative. We prove that a negative value exists so that if , the beta-spline functionsN_i(u) are positive. Moreover, if the control vertices are such that x₀ x_m−1, we have proved that the design curve keeps the properties already proved in the case β₂(i) 0.     

Final algebras, cosemicomputable algebras and degrees of unsolvability

This paper studies some computability notions for abstract data types, and in particular compares cosemicomputable many-sorted algebras with a notion of finality to model minimal-state realizations of abstract (software) machines. Given a finite many-sorted signature Σ and a set of V of visible sorts, for every Σ-algebra A with co-r.e. behavior and nontrivial, computable V-behavior, there is a finite signature extension Σ' of Σ (without new sorts) and a finite set E of Σ'-equations such that A is isomorphic to a reduct of the final (Σ', E)-algebra relative to V. This uses a theorem due to Bergstra and Tucker [3]. If A is computable, then A is also isomorphic to the reduct of the initial (Σ′, E)-algebra. We also prove some results on congruences of finitely generated free algebras. We show that for every finite signature Σ, there are either countably many Σ-congruences on the free Σ-algebra or else there is a continuum of such congruences. There are several necessary and sufficient conditions which separate these two cases. We introduce the notion of the Turing degree of a minimal algebra. Using the results above, we prove that there is a fixed one-sorted signature such that for every r.e. degree d, there is a finite set E of Σ-equations such the initial (Σ, E)-algebra has degree d. There is a two-sorted signature Σ₀ and a single visible sort such that for every r.e. degree d there is a finite set E of Σ-equations such that the initial (Σ, E, V)-algebra is computable and the final (Σ, E, V)-algebra is cosemicomputable and has degree d.     

McClellan transformation and the construction of biorthogonal wavelet bases of LR

Bidimensional wavelet bases are constructed by means of McClellan's transformation applied to a pair of one-dimensional biorthogonal wavelet filters. It is shown that under some conditions on the transfer function F(ω₁,ω₂) associated to the McClellan transformation and on the dilation matrix D, it is possible to construct symmetric compactly supported biorthogonal wavelet bases of L²(R²). Finally, the construction method is illustrated by means of numerical examples.     

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

On Spectral Bounds for the k-Partitioning of Graphs

When executing processes on parallel computer systems a major bottle-neck is interprocessor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of (|V|/2k)\sum ^k _i=1λ _i for the k-section width of a graph is well known. We show new relations between the structure and the eigenvalues of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define a global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor.     

Size of ordered binary decision diagrams representing threshold functions

An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. We consider two cases: the case when a variable ordering is given and the case when it is adaptively chosen. We show 1) O(2^n/2) upper bound for both cases, 2) Ω(2^n/2) lower bound for the former case and 3) Ω(n2^√n/2) lower bound for the latter case. We also show some relations between the variable ordering and the size of OBDDs representing threshold functions.     

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.