Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

Upper bounds on the queuenumber of k-ary n-cubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph G, denoted by qn(G), is called the queuenumber of G. Heath and Rosenberg [SIAM J. Comput. 21 (1992) 927-958] showed that boolean n-cube (i.e., the n-dimensional hypercube) can be laid out using at most n−1 queues. Heath et al. [SIAM J. Discrete Math. 5 (1992) 398-412] showed that the ternary n-cube can be laid out using at most 2n−2 queues. Recently, Hasunuma and Hirota [Inform. Process. Lett. 104 (2007) 41-44] improved the upper bound on queuenumber to n−2 for hypercubes. In this paper, we deal with the upper bound on queuenumber of a wider class of graphs called k-ary n-cubes, which contains hypercubes and ternary n-cubes as subclasses. Our result improves the previous bound in the case of ternary n-cubes. Let denote the n-dimensional k-ary cube. This paper contributes three main results as follows:

(1)

if n?3.

(2)

if n?2 and 4?k?8.

(3)

if n?1 and k?9.

     

The periodic nature of the positive solutions of a nonlinear fuzzy max-difference equation

We investigate the periodic nature of the positive solutions of the fuzzy difference equation , where k, m are positive integers, A₀, A₁, are positive fuzzy numbers and the initial values x_i, i = −d, −d + 1, … , −1, d = max{k, m}, are positive fuzzy numbers. In addition, we give conditions so that the solutions of this equation are unbounded.     

On the Euler sequence spaces which include the spaces ?p and ?∞ I

In the present paper, we introduce the Euler sequence space consisting of all sequences whose Euler transforms of order r are in the space ?_p of non-absolute type which is the BK-space including the space ?_p and prove that the spaces and ?_p are linearly isomorphic for 1 ? p ? ∞. Furthermore, we give some inclusion relations concerning the space . Finally, we determine the α-, β- and γ-duals of the space for 1 ? p ? ∞ and construct the basis for the space , where 1 ? p < ∞.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

How strong is Nisan?s pseudo-random generator?

We study the resilience of the classical pseudo-random generator (PRG) of Nisan (1992) [6] against space-bounded machines that make multiple passes over the input. Nisan?s PRG is known to fool log-space machines that read the input once. We ask what are the limits of this PRG regarding log-space machines that make multiple passes over the input. We show that for every constant k Nisan?s PRG fools log-space machines that make passes over the input, using a seed of length , for some k^′>k. We complement this result by showing that in general Nisan?s PRG cannot fool log-space machines that make nO(1) passes even for a seed of length . The observations made in this note outline a more general approach in understanding the difficulty of derandomizing BPNC¹.     

Conditional fault hamiltonian connectivity of the complete graph

A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and .     

Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths.     

Greedy algorithms for generalized k-rankings of paths

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2,…,k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let Pn be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of Pn. In this paper we investigate two generalizations of rankings. We first consider bounded (k,s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider kt-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number to be the smallest number of labels that can be used in a (k,s)-ranking and show for n?2, where i=⌊log₂(s)⌋+1. We define the kt-rank number, to be the smallest number of labels that can be used in a kt-ranking. We present a recursive formula that gives the kt-rank numbers for paths, showing for all an−1<j?an where {an} is defined as follows: a₁=1 and an=⌊((t+1)/t)an−1⌋+1.     

Invariance properties in the root sensitivity of time-delay systems with double imaginary roots

If is an eigenvalue of a time-delay system for the delay τ₀ then is also an eigenvalue for the delays τ_k?τ₀+k2π/ω, for any k∈Z. We investigate the sensitivity, periodicity and invariance properties of the root for the case that is a double eigenvalue for some τ_k. It turns out that under natural conditions (the condition that the root exhibits the completely regular splitting property if the delay is perturbed), the presence of a double imaginary root for some delay τ₀ implies that is a simple root for the other delays τ_k, k≠0. Moreover, we show how to characterize the root locus around . The entire local root locus picture can be completely determined from the square root splitting of the double root. We separate the general picture into two cases depending on the sign of a single scalar constant; the imaginary part of the first coefficient in the square root expansion of the double eigenvalue.     

Acyclic chromatic index of planar graphs with triangles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by , is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ(G). In this paper, we show that , if G contains no 4-cycle; , if G contains no intersecting triangles; and if G contains no adjacent triangles.     

How much precision is needed to compare two sums of square roots of integers?

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n^′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2).     

A tighter upper bound for random MAX 2-SAT

Given a conjunctive normal form F with n variables and m=cn 2-clauses, it is interesting to study the maximum number of clauses satisfied by all the assignments of the variables (MAX 2-SAT). When c is sufficiently large, the upper bound of of random MAX 2-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound (3/4)cn+g(c)cn also using the first-moment argument but correcting the error items for f(n,cn), and when considering the ε³ error item. Furthermore, we extrapolate the region of the validity of the first-moment method is c>2.4094 by analyzing the higher order error items.     

Space efficient secret sharing for implicit data security

This paper presents a k-threshold computational secret sharing technique that distributes a secret S into shares of size , where ∣S∣ denotes the secret size. This bound is close to the space optimal bound of if the secret is to be recovered from k shares. In other words, our technique can be looked upon as a new information dispersal scheme that provides near optimal space efficiency. The proposed scheme makes use of repeated polynomial interpolation and has potential applications in secure information dispersal on the Web and in sensor networks.     

The k-fundamental group of a closed k-surface

In this paper, we deal with the problem of computing the digital fundamental group of a closed k-surface by using various properties of both a (simple) closed k-surface and a digital covering map. To be specific, let be a simple closed k_i-curve with l_i elements in Z^n_i, i∈{1,2}. Then, the Cartesian product is not always a closed k-surface with some k-adjacency of Z^n₁+n₂. Thus, we provide a condition for to be a (simple) closed k-surface with some k-adjacency depending on the k_i-adjacency, i∈{1,2}. Besides, even if is not a closed k-surface, we show that the k-fundamental group of can be calculated by both a k-homotopic thinning and a strong k-deformation retract.     

Flexible coloring

Motivated by reliability considerations in data deduplication for storage systems, we introduce the problem of flexible coloring. Given a hypergraph H and the number of allowable colors k, a flexible coloring of H is an assignment of one or more colors to each vertex such that, for each hyperedge, it is possible to choose a color from each vertex?s color list so that this hyperedge is strongly colored (i.e., each vertex has a different color). Different colors for the same vertex can be chosen for different incident hyperedges (hence the term flexible). The goal is to minimize color consumption, namely, the total number of colors assigned, counting multiplicities. Flexible coloring is NP-hard and trivially approximable, where s is the size of the largest hyperedge, and n is the number of vertices. Using a recent result by Bansal and Khot, we show that if k is constant, then it is UGC-hard to approximate to within a factor of s−ε, for arbitrarily small constant ε>0. Lastly, we present an algorithm with an approximation ratio, where k^′ is number of colors used by a strong coloring algorithm for H.     

Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

A k-bounded pseudo-Boolean function is a real-valued function on n{0,1} that can be expressed as a sum of functions depending on at most k input bits. The k-bounded functions play an important role in a number of areas including molecular biology, biophysics, and evolutionary computation. We consider the problem of finding the Fourier coefficients of k-bounded functions, or equivalently, finding the coefficients of multilinear polynomials on n{−1,1} of degree k or less. Given a k-bounded function f with m non-zero Fourier coefficients for constant k, we present a randomized algorithm to find the Fourier coefficients of f with high probability in function evaluations. The best known upper bound was , where λ(n,m) is between and n depending on m. Our bound improves the previous bound by a factor of . It is almost tight with respect to the lower bound . In the process, we also consider the problem of finding k-bounded hypergraphs with a certain type of queries under an oracle with one-sided error. The problem is of self interest and we give an optimal algorithm for the problem.     

Minimizing the sum of the k largest functions in linear time

Given a collection of n functions defined on , and a polyhedral set , we consider the problem of minimizing the sum of the k largest functions of the collection over Q. Specifically we focus on collections of linear functions and several classes of convex, piecewise linear functions which are defined by location models. We present simple linear programming formulations for these optimization models which give rise to linear time algorithms when the dimension d is fixed. Our results improve complexity bounds of several problems reported recently by Tamir [Discrete Appl. Math. 109 (2001) 293-307], Tokuyama [Proc. 33rd Annual ACM Symp. on Theory of Computing, 2001, pp. 75-84] and Kalcsics, Nickel, Puerto and Tamir [Oper. Res. Lett. 31 (1984) 114-127].