International Journal of Foundations of Computer Science

Internet (IP) packet forwarding is typically done by finding the longest prefix in a router table that matches the packet's destination address. Although significant effort has been devoted to the development of data structures for static and dynamic router-tables for random packet-access-patterns, considerably less effort has been expended in the development of such structures for bursty access-patterns (i.e., streams of packets in which destination addresses repeat frequently within localized windows of packets). In this paper, we first formulate a variant, ACRBT (alternative collection of red-black trees), of the CRBT (collection of red-black trees) data structure proposed earlier for dynamic router-tables. By replacing the red-black trees used in the ACRBT with splay trees, we obtain the CST (collection of splay trees) structure in which search, insert, and delete take O(log n) amortized time per operation, where n is the number of prefixes in the router table. By replacing the front end of the CST with biased skip lists, we obtain the BSLPT (biased skip lists with prefix trees) structure in which search, insert, and delete take O(log n) expected time. The CST and BSLPT structures are designed so as to perform much better when the access pattern is bursty than when it is not. Experimental results using real IPv4 routing databases and synthetically generated search sequences as well as trace sequences are presented. For extremely bursty access patterns, the CST structure is best. Otherwise, the ACRBT is recommended. Our experiments also indicate that a supernode implementation of the ACRBT usually has better search performance than does the traditional one-element-per-node implementation.

We study the scheduling problem on a batch machine which is capable of processing a batch of jobs at a time. For a batch machine of capacity c, we designed an algorithm for minimizing the total completion time in O(n^6c) time (for sufficiently large c). This improves the best previous time bound of O(n^c(c-1)) given by Brucker et al [1]. We also designed a new algorithm with running time .

A quantum authentication scheme is presented in this paper. Two parties share Einstein-Podolsky-Rosen(EPR) pairs previously as the identification token. They create auxiliary EPR pairs to interact with the identification token. Then the authentication is accomplished by a complete Bell state measurement. This scheme is proved to be secure. If no errors and eavesdroppers exist in the transmission, the identification token is unchanged after the authentication. So it can be reused.

Remmel and Williamson recently defined a class of directed graphs, called filtered digraphs, and described a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions [12]. Filtered digraphs include many specialized graphs such as complete k-partite graphs. The Remmel-Williamson bijections provide explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. In this paper, we prove another important property of these bijections, namely, that it allows one to construct efficient algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs G. For example, we show that if G=(V,E) is a filtered digraph and SP(G) is the collection of spanning trees of G, then our algorithm requires O(|V|) operations of sum, difference, product, quotient, and comparison of numbers less than or equal |SP(G)| to rank or unrank spanning trees of G.

One of the well known Web search algorithms is HITS by Kleinberg [9]. We analyze the stability of HITS, when and how much outputs of HITS depend on initial values chosen by the algorithm. More importantly, we proposed a model for a type of hyperlink structures, which have been frequently observed on the Web, and we prove that in the model a crucial technical assumption made in HITS is satisfied, and accordingly HITS works well.

We define the number of productions and the number of symbols as measures of descriptional complexity for tabled interactionless Lindenmayer systems and their special cases. We investigate the decrease of the descriptional complexities if we go from a family to another one which has a larger generative capacity.

We present in this paper fast algorithms for the 3-D dominance reporting and counting problems, and generalize the results to the d-dimensional case. Our 3-D dominance reporting algorithm achieves O(log n/loglog n+f) query time using O(n log^∊ n) space, where f is the number of points satisfying the query and ∊>0 is an arbitrarily small constant. For the 3-D dominance counting problem (which is equivalent to the 3-D range counting problem), our algorithm runs in O((log n/loglog n)²) time using O(n log^1+∊n/loglog n) space.