A Criterion for Extractability of Mutual Information for a Triple of Strings

We say that the mutual information of a triple of binary strings a, b, c can be extracted if there exists a string d such that a, b, and c are independent given d, and d is simple conditional to each of the strings a, b, and c. It is proved that the mutual information between a, b, and c can be extracted if and only if the values of the conditional mutual informations I(a : b|c), I(a : c|b), and I(b : c|a) are negligible. The proof employs a non-Shannon-type information inequality (a generalization of the recently discovered Zhang–Yeung inequality).     

Stochastic adaptive pole-zero assignment with convergence analysis

The adaptive control u_n is designed for the stochastic system A(z)y_n+1 = B(z)u_n+C(z)w_n+1 with unknown constant matrix coefficients in the polynomials A(z), B(z) and C(z) in the shift-back operator with the purposes that (1) the unknown matrices are strongly consistently estimated and (2) the poles and zeros are replaced in such a way that the system itself is transferred to A⁰(z)y_n+1 = B⁰(z)u_n⁰+_n+1 with given A⁰(z), B⁰(z) and u_n⁰ so that the pole-zero assignment error {_n+1} is minimized. The problem of adaptive pole-zero assignment combined with tracking is also considered in this paper. Conditions used are imposed only on A(z), B(z) and C(z).     

A Simple Optimal Parallel Algorithm for a Core of a Tree

A core of a tree T = (V, E) is a path in T which minimizes ∑_vVd(v, P), where d(v, P), the distance from a vertex v to path P, is defined as min_uPd(v, u). We present an optimal parallel algorithm to find a core of T in O(log n) time using O(n/log n) processors on an EREW PRAM machine, where n is the number of vertices of tree T.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

Independence and k-domination in graphs

A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ _k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ _k (G). In particular, we show that, if G is connected with δ(G)≥k then γ _k (G)≤(Δ(G)?1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.     

Coincidental extension of scattered context languages

For a symbol, #, and a string, x = a ₁ a ₂ ...a _{n - 1} a _n , any string of the form # ⁱ a ₁ # ⁱ a ₂ # ⁱ...# ⁱ a _{n - 1} # ⁱ a _n # ⁱ, where 0, is a coincidental #-extension of x. A language, K, is a coincidental #-extension of L if every string of K represents a coincidental extension of a string in L and the deletion of all #s in K results in L. This paper proves that for every recursively enumerable language, E, there exists a propagating scattered context language that represents a coincidental extension of E. Received: 31 October 2001 / 31 January 2003     

Worst-case optimal algorithm for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set Q(D) of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use O(|D|) space and O(|Q||D|) time. Several previously known algorithms for the streaming version use Ω(dn) space and Ω(dn|D|) time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the O(|D|) space used by the in-memory algorithms. We present an efficient algorithm that uses O(d|Q|+nc) space and O((|Q|+dn)|D|) time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case.     

An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem

Let G=(VG,AG) be a digraph and let S ⊔ T be a bipartition of VG. A bibranching is a subset B⊆AG such that for each node s∈S there exists a directed s–T path in B and, vice versa, for each node t∈T there exists a directed S–t path in B.     

Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology

This paper discusses how to count and generate strings that are ``distinct' in two senses: p -distinct and b -distinct. Two strings x on alphabet A and x' on alphabet A' are said to be p -distinct iff they represent distinct ``patterns'; that is, iff there exists no one—one mapping from A to A' that transforms x into x' . Thus aab and baa are p -distinct while aab and ddc are p -equivalent. On the other hand, x and x' are said to be b -distinct iff they give rise to distinct border (failure function) arrays: thus aab with border array 010 is b -distinct from aba with border array 001 . The number of p -distinct (resp. b -distinct) strings of length n formed using exactly k different letters is the [k,n] entry in an infinite p' (resp. b' ) array. Column sums p[n] and b[n] in these arrays give the number of distinct strings of length n . We present algorithms to compute, in constant time per string, all p -distinct (resp. b -distinct) strings of length n formed using exactly k letters, and we also show how to compute all elements p'[k,n] and b'[k,n] . These ideas and results have application to the efficient generation of appropriate test data sets for many string algorithms. Received December 21, 1995; revised April 28, 1997.     

On the edge-tenacity of the middle graph of a graph

We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S)=[| S|+τ (G?S)]/[w(G?S)]. Formally, the edge-tenacity of a graph G is defined as T′(G)=min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T′-set of G if T′(G)=sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, τ(G?S) is the number of vertices in the largest component of G?S and w(G?S) is the number of components of G?S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.     

Exponential stability in mean square of neutral stochastic differential functional equations

The aim of this paper is to investigate the exponential stability in mean square for a neutral stochastic differential functional equation of the form d[x(t) − G(x_t)] = [f(t,x(t)) + g(t, x_t)]dt + σ(t, x_t)dw(t), where x_t = {x(t + s): − τ s 0}, with τ > 0, is the past history of the solution. Several interesting examples are a given for illustration.     

A class of hybrid collocation methods for third-order ordinary differential equations

A class of numerical methods is proposed for solving general third-order ordinary differential equations directly by collocation at the grid points x = x _n+j , i = 0(1)k and at an off grid point x = x _n+u , where k is the step number of the method and u is an arbitrary rational number in (x _n , x _n+k ). A predictor of order 2k ? 1 is also proposed to cater for y _n+k in the main method. Taylor series expansion is employed for the calculation of y _n+1, y _n+2, y _n+u and their higher derivatives. Evaluation of the resulting method at x = x _n+k for any value of u in the specified open interval yields a particular discrete scheme as a special case of the method. The efficiency of the method is tested on some general initial value problems of third-order ordinary differential equations.     

Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group

LetG andH be graphs with |V(G)≤ |V(H)|. Iff:V(G) →V(H) is a one-to-one map, we letdilation(f) be the maximum of dist _H (f x),f(y)) over all edgesxy inG where dist _H denotes distance inH. The construction of maps fromG toH of small dilation is motivated by the problem of designing small slowdown simulations onH of algorithms that were originally designed for the networkG. LetS(n), thestar network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent ifx o (1,i) =y for somei. That is,xy is an edge ifx andy are related by a transposition involving some fixed symbol (which we take to be 1). Also letP(n), thepancake network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent if one can be obtained from the other by reversing some prefix. That is,xy is an edge ifx andy are related byx o (1,i(2,i-1) ⋯ ([i/2], [i/2]) =y. The star network (introduced in [AHK]) has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages ofS(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The concern of this paper is to construct low dilation maps of hypercube networks into star or pancake networks. Typically in such problems, there is a tradeoff between keeping the dilationsmall and simulating alarge hypercube. Our main result shows that at the cost ofO (1) dilation asn→ ∞, one can embed a hypercube of near optimum dimension into the star or pancake networksS(n) orP(n). More precisely, lettingQ (d) be the hypercube of dimensiond, our main theorem is stated below. For simplicity, we state it only in the special case when the star network dimension is a power of 2. A more general result (applying to star networks of arbitrary dimension) is obtained by a simple interpolation. This author's research was done during the Spring Semester 1991, as a visiting professor in the Department of Mathematics and Statistics at Miami University.     

<Emphasis Type="Italic">f</Emphasis>-Sensitivity Distance Oracles and Routing Schemes

An f-sensitivity distance oracle for a weighted undirected graph G(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructible f-sensitivity distance oracle that given a triplet (s,t,F), where s and t are vertices and F is a set of forbidden edges such that |F|≤f, returns an estimate of the distance between s and t in G(V,E∖F). For an integer parameter k≥1, the size of the data structure is O(fkn ^1+1/k log (nW)), where W is the heaviest edge in G, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time is O(|F|⋅log ² n⋅log log n⋅log log d), where d is the distance between s and t in G(V,E∖F).     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

On the 1-fault hamiltonicity for graphs satisfying Ore's theorem and its generalization

Consider any undirected and simple graph G=(V, E), where V and E denote the vertex set and the edge set of G, respectively. Let |G|=|V|=n. The well-known Ore's theorem states that if deg_G(u)+deg_G(v)≥n+k holds for each pair of nonadjacent vertices u and v of G, then G is traceable for k=?1, hamiltonian for k=0, and hamiltonian-connected for k=1. Lin et al. generalized Ore's theorem and showed that under the same condition as above, G is r*-connected for 1≤r≤k+2 with k≥1. In this paper, we improve both theorems by showing that the hamiltonicity or r*-connectivity of any graph G satisfying the condition deg_G(u)+deg_G(v)≥n+k with k≥?1 is preserved even after one vertex or one edge is removed, unless G belongs to two exceptional families.     

Rational Solutions of Riccati-like Partial Differential Equations

When factoring linear partial differential systems with a finite-dimensional solution space or analysing symmetries of nonlinear ODEs, we need to look for rational solutions of certain nonlinear PDEs. The nonlinear PDEs are called Riccati-like because they arise in a similar way as Riccati ODEs. In this paper we describe the structure of rational solutions of a Riccati-like system, and an algorithm for computing them. The algorithm is also applicable to finding all rational solutions of Lie’s system { ∂_xu + u² + a₁u + a₂v + a₃, ∂_yu + uv + b₁u + b₂v + b₃, ∂_xv + uv + c₁u + c₂v + c₃, ∂_yv + v² + d₁u + d₂v + d₃},where a₁, . . . , d₃are rational functions of x and y.     

Algorithms for (0, 1, d)-graphs with d constrains

Let G be a graph with vertex set V(G). Let n, k, d be non-negative integers such that n+2k+d≤|V(G)|?2 and |V(G)|?n?d are even. A matching which saturates exactly |V(G)|?d vertices is called a defect-d matching of G. If when deleting any n vertices the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be an (n, k, d)-graph. We present an algorithm to determine (0, 1, d)-graphs with d constraints. Moreover, we solve the problem of augmenting a bipartite graph G=(B, W) to be a (0, 1, d)-graph by adding fewest edges, where d=∥B|?|W∥. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.     

The maximum gain of increasing the number of preemptions in multiprocessor scheduling

We consider the optimal makespan C(P, m, i) of an arbitrary set P of independent jobs scheduled with i preemptions on a multiprocessor with m identical processors. We compare the ratio for such makespans for i and j preemptions, respectively, where i < j. This ratio depends on P, but we are interested in the P that maximizes this ratio, i.e. we calculate a formula for the worst case ratio G(m, i, j) defined as G(m,i,j)=max\fracC(P,m,i)C(P,m,j),{G(m,i,j)=\max \frac{C(P,m,i)}{C(P,m,j)},} where the maximum is taken over all sets P of independent jobs.