Search

We investigate a recently introduced width measure of planar shapes called sweepwidth and prove a lower bound theorem on the sweep-width. [ABSTRACT FROM AUTHOR]

We propose a novel computational problem on undirected graphs, prove that it is NPcomplete, and design a linear-time algorithm for the special case when the graph is a cactus. The decision version of the problem is, given a graph and a train in it, the train being an edge sequence that forms a path with one vertex designated as the locomotive, can the train reach a certain target vertex, or not? The movement of the train consists of elementary, single-edge moves with the locomotive forward, the length of the train staying the same. Further, the movement of the train is restricted: the train cannot self-intersect [ABSTRACT FROM AUTHOR]

To reconstruct a graph from some of its elements or characteristics is a hard problem. Reconstructions require very good mathematical background and programming skills. That is why some not so difficult graph reconstruction problems may be appropriate for competitions in programming both for university and school students. In this paper two such problems are considered - reconstruction of a tree from the distances between its outer vertices and from the distances between all its vertices. It is proved that any tree can be reconstructed in either case. The corresponding algorithms are presented and their time complexities are estimated. [ABSTRACT FROM AUTHOR]

We introduce a novel approach to the classical problem of the in situ, stable merging of lists, where ‘in situ’ means the use of no more than $O(\log^2 n)$ bits of extra memory for lists of size $n$. Our algorithm, Shufflemerge, reduces the merging problem to the problem of realizing the ‘perfect shuffle’ permutation, that is, the exact interleaving of two, equal length lists. The algorithm is recursive and so uses a logarithmic number of variables. Thus it uses more than ‘absolutely minimum storage’, i.e. $O(\log n)$ bits. A simple method of realizing the perfect shuffle uses one extra bit per element, and so is not in situ. We show that the perfect shuffle can be attained using absolutely minimum storage and in linear time, at the expense of doubling the number of moves, relative to the simple method. We note that there is a worst case for Shufflemerge requiring time $\Omega(n \log n)$, where $n$ is the sum of the lengths of the input lists. We also present an analysis of a variant of Shufflemerge which uses a generalized shuffle and which has a provable average case time complexity of $O(n\log \log m)$, where $m$ is the length of the shortest input list. It is unlikely that the generalized shuffle can be achieved in situ. Linear time, in situ, stable merging has previously been demonstrated. We present experimental evidence indicating that Shufflemerge, although almost certainly not asymptotically linear, might be of value in practice. The relative simplicity of the basic method, particularly with respect to stability, also recommends it. [ABSTRACT FROM PUBLISHER]