A (colored) choice dictionary is a data structure that is initialized with positive integers n and c and subsequently maintains a sequence of n elements of {0,...,c-1}, called colors, under operations to inspect and to update the color in a given position and to return the position of an occurrence of a given color. Choice dictionaries are fundamental in space-efficient computing. Some applications call for the additional operation of dynamic iteration, i.e., enumeration of the positions containing a given color while the sequence of colors may change. An iteration is robust if it enumerates every position that contains the relevant color throughout the iteration but never enumerates a position more than once or when it does not contain the color in question. We describe the first choice dictionary that executes every operation in constant amortized time and almost robust iteration in constant amortized time per element enumerated. The iteration is robust, except that it may enumerate some elements a second time. The data structure occupies n log_2 c+O((log n)^2) bits. The time and space bounds assume that c=O((log n)^{1/2}(log log n)^{-{3/2}}).

The choice dictionary is introduced as a data structure that can be initialized with a parameter $n\in\mathbb{N}=\{1,2,\ldots\}$ and subsequently maintains an initially empty subset $S$ of $\{1,\ldots,n\}$ under insertion, deletion, membership queries and an operation choice that returns an arbitrary element of $S$. The choice dictionary appears to be fundamental in space-efficient computing. We show that there is a choice dictionary that can be initialized with $n$ and an additional parameter $t\in\mathbb{N}$ and subsequently occupies $n+O(n(t/w)^t+\log n)$ bits of memory and executes each of the four operations insert, delete, contains (i.e., a membership query) and choice in $O(t)$ time on a word RAM with a word length of $w=Ω(\log n)$ bits. In particular, with $w=Θ(\log n)$, we can support insert, delete, contains and choice in constant time using $n+O(n/(\log n)^t)$ bits for arbitrary fixed $t$. We extend our results to maintaining several pairwise disjoint subsets of $\{1,\ldots,n\}$. We study additional space-efficient data structures for subsets $S$ of $\{1,\ldots,n\}$, including one that supports only insertion and an operation extract-choice that returns and deletes an arbitrary element of $S$. All our main data structures can be initialized in constant time and support efficient iteration over the set $S$, and we can allow changes to $S$ while an iteration over $S$ is in progress. We use these abilities crucially in designing the most space-efficient algorithms known for solving a number of graph and other combinatorial problems in linear time. In particular, given an undirected graph $G$ with $n$ vertices and $m$ edges, we can output a spanning forest of $G$ in $O(n+m)$ time with at most $(1+ε)n$ bits of working memory for arbitrary fixed $ε>0$.

We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of \Theta(\log\log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.

For t >0 and g ≥0, a vertex-weighted graph of total weight W is ( t , g ) -trimmable if it contains a vertex-induced subgraph of total weight at least (1−1/ t ) W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t >0, there is a constant g ≥0 such that every vertex-weighted graph in the family is ( t , g )-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.

Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of $$ \Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right) $$ characters in the worst case.

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range O. .2W -1 in O (n log log n) time, for arbitrary w z log n, a significant improvement over the bound of O (n-) achieved by the fusion trees of Fredman and Willard.Provided that w 2 (log n)z+', for some fixed e > 0, the sorting can even be accomplished in linear expected time with a randomized algorithm.Both of our algorithms parallelize without loss on a unitcost PRAM with a word length of w bits.The first one yields an algorithm that uses O (log n) time and O (n log log n) operations on a deterministic CRCW PRAM.The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w 2 (log n)2+' for some fixed c >0.Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.

We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n-vertex input graphs, the algorithm works in O((log n) 2 ) time using O(n) operations on the EREW PRAM. We also give faster parallel algorithms with optimal speedup for the problem of deciding whether the treewidth of an input graph is bounded by a given constant and for a variety of problems on graphs of bounded treewidth, including all decision problems expressible in monadic second-order logic. On n-vertex input graphs, the algorithms use O(n) operations together with O(log n log * n) time on the EREW PRAM, or O(log n) time on the CRCW PRAM.

We show that a maximum flow in a network with n vertices can be computed deterministically in $O({{n^3 } / {\log n}})$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3 )$. The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is $O(n^{{8 / 3}} (\log n)^{{4 / 3}} )$, in contrast with $\Omega (nm)$ flow operations for all previous algorithms, where m denotes the number of edges in the network. A randomized version of our algorithm executes $O(n^{{3 / 2}} m^{{1 / 2}} \log n + {{n^2 (\log n)^2 } / {\log }}(2 + {{n(\log n)^2 } / m})$ flow operations with high probability. For the special case in which all capacities are integers bounded by U, we show that a maximum flow can be computed deterministically using $O(n^{{3 / 2}} m^{{1 / 2}} + n^2 (\log U)^{{1 / 2}} + \log U$ flow operations and $O(\min \{ {{nm,n^3 } / {\log n\} + n^2 }}(\log U)^{{1 / 2}} + \log U)$ time. We finally argue that several of our results yield parallel algorithms with optimal speedup.

A randomized algorithm for computing a maximum flow is presented. For an n-vertex m-edge network, the running time is $O(nm + n^{2}(\log n)^{2})$ with probability at least $1-2^{-\sqrt {nm}}$. The algorithm is always correct, and in the worst case runs in $O(nm \log n)$ time. The only use of randomization is to randomly permute the adjacency lists of the network vertices at the start of the execution. The analysis introduces the notion of premature target relabeling (PTR) events and shows that each PTR event contributes $O(\log n)$ amortized time to the overall running time. The number of PTR events is always $O(nm)$; however, it is shown that when the adjacency lists are randomly permuted, then this quantity is $O(n^{3/2}m^{1/2} + n^{2} \log n)$ with high probability.

Article Free Access Share on The complexity of searching a sorted array of strings Authors: Arne Andersson Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden Department of Computer Science, Lund University, Box 118, 22100 Lund, SwedenView Profile , Torben Hagerup Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, GermanyView Profile , Johan Håstad Department of Computer Science, Royal Institute of Technology, 10044 Stockholm, Sweden Department of Computer Science, Royal Institute of Technology, 10044 Stockholm, SwedenView Profile , Ola Petersson Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden and Department of Mathematics, Statistics and Computer Science, Växjö University, 35195 Växjö, Sweden Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden and Department of Mathematics, Statistics and Computer Science, Växjö University, 35195 Växjö, SwedenView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 317–325https://doi.org/10.1145/195058.195175Published:23 May 1994Publication History 6citation285DownloadsMetricsTotal Citations6Total Downloads285Last 12 Months16Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Optimal parallel string algorithms: sorting, merging and computing the minimum Author: Torben Hagerup Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, GermanyView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 382–391https://doi.org/10.1145/195058.195202Published:23 May 1994Publication History 11citation707DownloadsMetricsTotal Citations11Total Downloads707Last 12 Months23Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Padded sorting requires n input keys to be output in sorted order in an array with slightly more than n locations, unused locations being filled with a special null value.We show that a deterministic CRCW PRAM with h processors can padded-sort n keys in ~(log log k)s .2°(*0g" '-lOg* '+1) time, for any k with 4 s k s n, which is close to a known lower bound of Q(log n/log k).As a consequence, we are able to improve the best previous result on deterministic sublogarithmic standard sorting.Other results include deterministic algorithms with optimal speedup for approximate prefix summation and for padded-sorting independent uniformly distributed random variables.In the first case the running time is O((log log n)4/log log log n), and in the second case the average running time is O((log log log n)4 /log(4) n).

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.

Conventional parallel sorting requires the n input keys to be output in an array of size n, and is known to take Omega (log n/log log n) time using any polynomial number of processors. The lower bound does not apply to the more 'wasteful' convention of padded sorting, which requires the keys to be output in sorted order in an array of size (1+o(1))n. The authors give very fast randomised CRCW PRAM algorithms for several padded-sorting problems. Applying only pairwise comparisons to the input and using kn processors, where 2>

hash function for a (multi) set X of n injective function h : X + {1,..., s}, where s = O(n), that can be stored in O(n) space and evaluated in constant time by a single processor.We show that a perfect hash function for a given multiset of n integers can be constructed optimally in O(log'n) time using O(n/log*n) processors.Our algorithm is faster than all previously published methods.More significantly, it is highly reliable: Whereas analyses of previous fast parallel hashhg schemes provided bounds on the expected resource requirements only, our algorithm is guaranteed to stay within the bounds given with overwhelming probability.be the most reliable sequential algorithm known for the static hashing problem.Moreover, our fastest running time of O(log*n) matches a lower bound established by

We investigate a nonstandard output convention for sorting.Specifically, the input elements are to be returned not in an array sorted in nondecrea.singorder, but in a linked list sorted in nondecreasing order.This problem, which we call chuin-sorting, may be viewed as standard sorting "minus" list ranking, the elements of Bi in this bucket through a random "dart throwing" process.The third part is similar to ordered chaining.The same three parts can be distinguished in the algorithms of (Rajasekaran and Reif, 1989).Whenever we speak of randomly choosing an element from a set without explicitly mentioning a probability distribution, the uniform distribution over the relevant set is to be understood.Form61Nand V~{l ,..., m}, define MAXGAPm(V) as the size of the largest set disjoint from V and of the form {a, . ...b} or {b, . ...m. l,a}, ,a}, where a, bE {l,... ,m}, ora8zeroif V= {l,... ,rn}.Fact 1: Let m and k be integers with 1 < k < m and let V be a set chosen randomly from the uniform distribution over all k-element subsets of {1,..., m}.Then for every r ~O, Pr(MAXGAPm(V) ~?') ~me-rkJm.Fact 2 (Chernoff bounds): For every binomially distributed random variable S, (a) Pr(S ~2E(S)) ~e-~is)i'; (b) Pr(S < 17( S)/2) ~e-E(s)i8; (c) For every r ~6.E(S), Pr(S ~r) ~2-".Fact 3: Let m, S,V E IN and let 21,1, . .., Zm,V be independent and uniformly

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/)>

Article Efficient parallel computation of arrangements of hyperplanes in d dimensions Share on Authors: Torben Hagerup Fachbereich 10, Informatik, Universität des Saarlandes, D-6600 Saarbrücken Fachbereich 10, Informatik, Universität des Saarlandes, D-6600 SaarbrückenView Profile , H. Jung Sektion Mathematik, Humboldt-Universität Berlin, PF 1297, DDR-1086, Berlin Sektion Mathematik, Humboldt-Universität Berlin, PF 1297, DDR-1086, BerlinView Profile , E. Welzl Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33 Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33View Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 290–297https://doi.org/10.1145/97444.97696Published:01 May 1990 4citation234DownloadsMetricsTotal Citations4Total Downloads234Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

It is shown that, in the PRIORITY CROW PRAM model and for the class of undirected embedded planar graphs, depth-first search (DFS) trees are no more difficult to construct than breadth-first search (BFS) trees. Specifically, suppose that time $T(n)\geqq \log n$ and $p(n)$ processors suffice to construct a planar embedding of a planar graph on n vertices and to compute a BFS tree of an undirected connected planar graph on $3n$ vertices. Then, given an undirected connected planar graph G on n vertices, a DFS tree of G can be computed in the stated model in $O(T(n))$ time with $p(n)$ processors. By using known results for the above problems, a DFS tree construction algorithm that runs in $O(\log n)$ time and uses $O(n^{3})$ processors is derived. The fastest previously known algorithm has time and processor bounds of $O({(\log n)}^2)$ and $O(n)$, respectively.

The authors present a randomized maximum-flow algorithm, called the PLED (prudent linking excess diminishing) algorithm, whose expected running time is O(nm+n/sup 2/(log n)/sup 3/); this is O(nm) for all except relatively sparse networks. The algorithm is always correct, and in the worst case, which occurs with negligible probability, it take O(nm log n) time. The approach taken is to maintain a parameter Delta , which is a measure of the maximum flow excess of a vertex and of the maximum amount of flow sent by a single operation. Initially, Delta is less than or equal to the maximum edge capacity, and Delta =0 at termination. The execution of the PLED algorithm is partitioned into phases so that Delta stays fixed during each phase and decreases between consecutive phases. In order to achieve a bound on the number of phases that is independent of the maximum edge capacity, the algorithm decreases Delta by as large a factor (>or=2) as possible, rather than by a constant factor. The algorithm uses the dynamic trees data structure.>

We show that a 5-colouring of the vertices of an n-vertex planar graph may be computed in $O(\log n\log ^ * n)$ time by an exclusive-read exclusive-write parallel RAM with $O({n / {(\log n\log ^ * n)}})$ processors. Our algorithm, while faster than all previously known methods, is at the same time the first parallel 5-colouring algorithm to exhibit an optimal speedup. Optimality is achieved through a method based on the accelerating cascades technique and of independent interest. It should be emphasized that although input to the algorithm is a planar graph, we do not require a planar embedding to be given as part of the input. Other results concern the colouring of graphs of bounded genus and the construction of search structures for triangular planar subdivisions.

We describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM’s shared memory is polynomial in n, each PRAM step is simulated by $O(\log n)$ MPC steps or by $O((\log n)^2 )$ steps of the bounded-degree network.This improves upon a previous result by Upfal and Wigderson. We also prove an $\Omega ({{(\log n)^2 } / {\log \log n}})$ lower bound on the number of steps needed to simulate one PRAM step on a bounded-degree network under the assumption that the communication in the network is point to point. As an important part of the simulation of PRAMs on MPCs, we use a new technique for dynamically averaging out a given work load among a set of processors operating in parallel.