Efficient algorithms for single- and two-layer linear placement of parallel graphs

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.     

Parallel communications for ATM network control and management

This paper describes an end-to-end parallel communications scheme based on a vector routing algorithm (VRA) for ATM network control and management. An information string is partitioned into m parts, which are then coded into k > m parts and sent out on k separate subchannels to the receiver. When m of the k parts are received correctly, the original information can be reconstructed. Two desirable effects are achieved in the context of ATM traffic control: (1) the burstiness of the source traffic can be smoothed out by the partition process; (2) the quality of service in terms of error, loss and delay can be controlled using the number of redundant routes k — m as a control parameter. Our results show that VRA is especially suitable for services with highly bursty traffic. We argue that several network management issues, including reliability, evolution and integration, security, and administration and billing can be addressed in a simple manner using the VRA framework.     

(h,k)-Arbiters for h-out-of-k mutual exclusion problem

h-Out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1hk) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k+1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k+1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.     

Contrast-optimal k out of n secret sharing schemes in visual cryptography

Visual cryptography and (k,n)-visual secret sharing schemes were introduced by Naor and Shamir (Advances in Cryptology — Eurocrypt 94, Springer, Berlin, 1995, pp. 1–12). A sender wishing to transmit a secret message distributes n transparencies amongst n recipients, where the transparencies contain seemingly random pictures. A (k,n)-scheme achieves the following situation: If any k recipients stack their transparencies together, then a secret message is revealed visually. On the other hand, if only k−1 recipients stack their transparencies, or analyze them by any other means, they are not able to obtain any information about the secret message. The important parameters of a scheme are its contrast, i.e., the clarity with which the message becomes visible, and the number of subpixels needed to encode one pixel of the original picture. Naor and Shamir constructed (k,k)-schemes with contrast 2^−(k−1). By an intricate result from Linial (Combinatorica 10 (1990) 349–365), they were also able to prove the optimality of these schemes. They also proved that for all fixed kn, there are (k,n)-schemes with contrast . For k=2,3,4 the contrast is approximately and . In this paper, we show that by solving a simple linear program, one is able to compute exactly the best contrast achievable in any (k,n)-scheme. The solution of the linear program also provides a representation of a corresponding scheme. For small k as well as for k=n, we are able to analytically solve the linear program. For k=2,3,4, we obtain that the optimal contrast is at least and . For k=n, we obtain a very simple proof of the optimality of Naor's and Shamir's (k,k)-schemes. In the case k=2, we are able to use a different approach via coding theory which allows us to prove an optimal tradeoff between the contrast and the number of subpixels.     

Computing LOGCFL certificates

The complexity class LOGCFL consists of all languages (or decision problems) which are logspace reducible to a context-free language. Since LOGCFL is included in AC¹, the problems in LOGCFL are highly parallelizable.

By results of Ruzzo (JCSS 21 (1980) 218), the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomially sized accepting computation trees. We show that for each such ATM M recognizing a language A in LOGCFL, it is possible to construct an L^LOGCFL transducer T_M such that T_M on input w A outputs an accepting tree for M on w. It follows that computing single LOGCFL certificates is feasible in functional AC¹ and is thus highly parallelizable.

Wanke (J. Algorithms 16 (1994) 470) has recently shown that for any fixed k, deciding whether the treewidth of a graph is at most k is in the complexity-class LOGCFL. As an application of our general result, we show that the task of computing a tree-decomposition for a graph of constant treewidth is in functional LOGCFL, and thus in AC¹.

We also show that the following tasks are all highly parallelizable: Computing a solution to an acyclic constraint satisfaction problem; computing an m-coloring for a graph of bounded treewidth; computing the chromatic number and minimal colorings for graphs of bounded tree- width.     

Product from solutions for multiserver centres with concurrent classes of customers

The MultiServer centre with Concurrent Classes of Customers (MSCCC) is a service centre consisting of B parallel identical exponential servers. The customers requesting service at the MSCCC centre belong to K groups. Customers arriving at the MSCCC centre are queued in the order of their arrival. A customer from group k will go into service at the MSCCC centre provided that one or more of the B servers is free and that at most n − 1 other group k customers are in service at the MSCCC centre.

The MSCCC centre can be applied to model systems where customers simultaneously occupy two resources. The system resources are partitioned into K primary and B secondary resources. A customer of group k can access primary resource k if it already is in possession of a secondary resource and if at most n − 1 other group k customers are using primary resource k.

This paper defines the MSCCC centre and presents several examples of computer (sub)systems that can be modelled using the MSCCC centre. The MSCCC centre is shown to satisfy local balance: therefore a multiclass queuing network consisting of BCMP and MSCCC centres has a product form solution. The joint probability distribution (JPD) for a queuing network consisting of several BCMP centres and one MSCCC centre is derived. Aggregation techniques are next used to reduce the JPD to a computationally tractable form. A Mean Value Analysis algorithm is presented for calculating the closed and open chain performance measures at the MSCCC centre.     

Ray representation for k-trees

k-trees have established themselves as useful data structures in pattern recognition. A fundamental operation regarding k-trees is the construction of a k-tree. We present a method to store an object as a set of rays and an algorithm to convert such a set into a k-tree. The algorithm is conceptually simple, works for any k, and builds a k-tree from the rays very fast. It produces a minimal k-tree and does not lead to intermediate storage swell.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

On the k-path partition of graphs

The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs.     

k元n方体的条件强匹配排除

为了度量发生故障时k元n方体对其可匹配性的保持能力,通过剖析条件故障下使得k元n方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得k元n方体不可匹配所需的最小故障数。当k ≥ 4为偶数且n ≥ 2时,得出了k元n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当k ≥ 3为奇数且n ≥ 2时,给出了该k元n方体容错性参数的一个可达下界和一个可达上界。结果表明,选取k为奇数的k元n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2n时仍是可匹配的,要使该系统不可匹配至多需要4n-3个故障元。     

Enabling structural summaries for efficient update and workload adaptation

To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from data and serve as the indexes for evaluating path expressions. We introduce D(k)-index, an adaptive structural summary, for general graph-structured data. Building on previous 1-index and A(k)-index, D(k)-index is also based on the concept of bisimilarity. However, as a generalization of 1-index and A(k)-index, D(k)-index possesses the adaptive ability to adjust its structure to changes in query load. It also enables efficient update algorithms, which are crucial to real applications but have not been adequately addressed in previous literatures. Our experiments show that D(k)-index is a more effective structural summary than previous static ones as a result of its query load sensitivity. In addition, the update operations on it can be performed more efficient than on its predecessors.     

Fast, long-lived renaming improved and simplified

In the long-lived M-renaming problem, N processes repeatedly acquire and release names ranging over {0, …, M − 1}, where M < N. It is assumed that at most k M processes concurrently request or hold names. Efficient solutions to the long-lived renaming problem can be used to improve the performance of applications in which processes repeatedly perform computations whose time complexity depends on the size of the name space containing the processes that participate concurrently. In this paper, we consider wait-free solutions to the long-lived M -renaming problem that use only read and write instructions in an asynchronous, shared-memory multiprocessor. A solution to long-lived renaming is fast if the time complexity of acquiring and releasing a name once is independent of N. We present a new fast, long-lived (k(k + 1)/2)renaming algorithm that significantly improves upon the time and space complexity of similar previous algorithms, while providing a much simpler solution. We also show that fast, long-lived (2k − 1)-renaming can be implemented with reads and writes. This result is optimal with respect to the size of the name space.     

Algorithms for generalized vertex-rankings of partial k-trees

A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. A c-vertex-ranking is optimal if the number of labels used is as small as possible. We present sequential and parallel algorithms to find an optimal c-vertex-ranking of a partial k-tree, that is, a graph of treewidth bounded by a fixed integer k. The sequential algorithm takes polynomial-time for any positive integer c. The parallel algorithm takes O(log n) parallel time using a polynomial number of processors on the common CRCW PRAM, where n is the number of vertices in G.     

k-Anonymization with Minimal Loss of Information

The technique of k-anonymization allows the releasing of databases that contain personal information while ensuring some degree of individual privacy. Anonymization is usually performed by generalizing database entries. We formally study the concept of generalization, and propose three information-theoretic measures for capturing the amount of information that is lost during the anonymization process. The proposed measures are more general and more accurate than those that were proposed by Meyerson and Williams and Aggarwal et al. We study the problem of achieving k-anonymity with minimal loss of information. We prove that it is NP-hard and study polynomial approximations for the optimal solution. Our first algorithm gives an approximation guarantee of O(ln k) for two of our measures as well as for the previously studied measures. This improves the best-known O(k)-approximation in. While the previous approximation algorithms relied on the graph representation framework, our algorithm relies on a novel hypergraph representation that enables the improvement in the approximation ratio from O(k) to O(ln k). As the running time of the algorithm is O(n^2k}), we also show how to adapt the algorithm in in order to obtain an O(k)-approximation algorithm that is polynomial in both n and k.     

High-order implicit blending surfaces of low degree

The applicability of the so-called potential method for blending implicitly defined surfaces is extended. The extended method is able to produce blendings which are C^k-continuous, where k may be chosen arbitrarily large. The blendings consist of piecewise algebraic surfaces of low degree. Specifically, the degree is k + 1 for so-called convex corners, and 2k for an important class of non-convex corners. In general the degree is linear in k, the constant of proportionality depending on the geometry of the corner. The method is illustrated by a concrete example, where a C² blending surface of degree 4 is constructed for a certain non-convex corner.     

New results on oscillation for delay differential equations with piecewise constant argument

We introduce a new technique to obtain some new oscillation criteria for the oscillating coefficients delay differential equation with piecewise constant argument of the form x′(t) + a(t)x(t) + b(t)x({t − k}) = 0, where a(t) and b(t) are right continuous functions on [−k, ∞), k is a positive integer, and [·] denotes the greatest integer function. Our results improve and generalize the known results in the literature. Some examples are also given to demonstrate the advantage of our results.     

On space-efficient algorithms for certain NP-complete problems

Some recent results claimed the existence of a class of algorithms for certain NP-complete problems, with running time O(n^{1g k} 2^n/2) and storage requirements O(k 2^n/k), for 2 kn. In this note we show that those results do not hold, implying that an algorithm with time O(n 2^n/2) and space O(2^n/4) is still the best-known solution for such class of NP-complete problems.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

On the number of occurrences of all short factors in almost all words

We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k(n) over A as n→∞, provided limsup_n→∞ k(n)/log n<1/log m.

In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where lim_n→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0.     

A learning scheme for a fuzzy k-NN rule

The performance of a fuzzy k-NN rule depends on the number k and a fuzzy membership-array W[l,m_R], where l and m_R denote the number of classes and the number of elements in the reference set X_R respectively. The proposed learning procedure consists in iterative finding such k and W which minimize the error rate estimate by the leaving ‘leaving one out‘ method.