An efficient parity detection technique using the two-moduli set {2 − 1, 2 + 1}

Lu and Chiang used both the table lookup and fractional number approaches to discover the parity of an RNS number. To eliminate the need for table space and time for computing fractions, a two-moduli set {2^h − 1, 2^h + 1} is used to speed up the technique proposed by Lu and Chiang. Based on this modified two-moduli set, it is found that the parity of an RNS number X = (x₁, x₂) is if x₁ ? x₂. On the contrary, if x₁ < x₂, the parity of X is .     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

A note on stutter-invariant PLTL

Peled and Wilke proved that every stutter-invariant propositional linear temporal property is expressible in Propositional Linear Temporal Logic (PLTL) without  ?  (next) operators. To eliminate next operators, a translation τ which converts a stutter-invariant PLTL formula ? to an equivalent formula τ(?) not containing  ?  operators has been given. By τ, for any formula , where φ contains no  ?  operators, a formula with the length of O(n⁴|φ|) is always produced, where n is the number of distinct propositions in ?, and |φ| is the number of symbols appearing in φ. Etessami presented an improved translation τ^′. By τ^′, for , a formula with the length of O(n×n²|φ|) is always produced. We further improve Etessami's result in the worst case to O(n×n²|φ|) by providing a new translation τ^″, and we show that the worst case will never occur.     

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

Super-connected and super-arc-connected Cartesian product of digraphs

We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained:

(i)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=κ(Di) for i=1,2, then D₁×D₂ is super-κ if and only if ,

(ii)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=λ(Di) for i=1,2, then D₁×D₂ is super-λ if and only if ,

where λ(D)=δ(D)=1, denotes the complete digraph of order n and n?2.