We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label length and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different tradeoffs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades. More specifically, we present a distance labeling scheme with labels of length bits1 and constant decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size (log 3)n and O(n/log n) decoding time, and Gavoille et al. (SODA'01), which uses labels of size 11n + o(n) and O(log log n) decoding time. In addition, our algorithm is simpler than the previous ones. In the case of integral edge weights of size at most W, we present almost matching upper and lower bounds for the label size . Furthermore, for r-additive approximation labeling schemes, where distances can be off by up to an additive constant r, we present both upper and lower bounds. In particular, we present an upper bound for 1-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency labeling scheme, namely n/2. We also give results for bipartite graphs as well as for exact and 1-additive distance oracles.

We show how to reduce the time overhead for implementing two-way movement on a singly linked list to O ( n ϵ ) per operation without modifying the list and without making use of storage other than a finite number of pointers into the list. We also prove a matching lower bound.These results add precision to the intuitive feeling that doubly linked lists are more efficient than singly linked lists, and quantify the efficiency gap in a read-only situation. We further analyze the number of points of access into the list (pointers) necessary for obtaining a desired value of ϵ. We obtain tight tradeoffs which also separate the amortized and worst-case settings.Our upper bound implies that read-only programs with singly-linked input can do string matching much faster than previously expected.

The following simulations by machines equipped with a one-way input tape and additional queue storage are shown: Every nondeterministic single-tape Turing machine (no separate input-tape) with time bound $t(n)$ can be simulated by one queue in $O(t(n))$ time. Every deterministic machine with a one-turn pushdown store can be simulated deterministically by one queue in $O(n\sqrt{n})$ time. Every Turing machine with several multidimensional tapes accepting with time bound $t(n)$ can be simulated by two queues in $O(t(n) \log^2 t(n))$ time. Every deterministic Turing machine with several linear tapes accepting with time bound $t(n)$ can be simulated deterministically in time $O(t(n) \log t(n))$ by a queue and a pushdown store. The first two results appear to be the first subquadratic simulations of other storage devices by one queue.

two-way movement in the input, nor tables or other types of auxiliary memory are available.We show how to reduce the time overhead for backingThe main result of this paper is a method for reducup in a singly linked list to O(n') per operation for any ing the time overhead for backing up in a linear list.e > 0 without modifying the list and without making More specifically for every E > 0 the time complexity use of storage other than a finite number of pointers into of backing up by one position in a singly linked list the list.We also prove a matching lower bound.Our of length n can be reduced to 0(n<).There are some results add precision to the intuitive feeling that doubly preparatory operations that take linear time, but since linked lists are more efficient than singly linked lists, merely inspecting the input takes linear time, the worst and quantify the efficiency gap in a read-only situation.case complexity of any reasonable program will not suf-As an application, our upper bound implies that readfer from these operations.We will therefore assume only programs can do string matching much faster than throughout this paper that the time complexity of all previously expected.programs to be simulated is at least linear.