Finding the connected components of an undirected graphG=(V, E) onn=|V| vertices andm=|E| edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs inO(log2 n) time usingn2/log2 nprocessors. For the CRCW PRAM model, in which concurrent writing is permitted, the best known algorithm runs inO(log n) time using slightly more than (n+m)/log nprocessors. Simulating this algorithm on the weaker CREW model increases its running time toO(log2 n). We present here a simple algorithm that runs inO(log3/2 n) time usingn+mCREW processors. Finding ano(log2 n) parallel connectivity algorithm for this model was an open problem for many years.

No abstract available.

We present an upper bound on the performance provided by a protocol guaranteeing mutually exclusive access to a replicated resource in a network subject to component failure and subsequent partitioning. The bound is presented in terms of the performance of a single resource in the same network. The bound is tight and is the first such bound known to us. Since mutual exclusion is one of the requirements for maintaining the consistency of a database object, this bound provides an upper limit on the availability provided by any database consistency control protocol, including those employing dynamic data relocation and replication. We show that if a well-placed single copy provides availability A for 0 ≤ A ≤ 1, then no scheme can achieve availability greater than √A in the same network. We show this bound to be the best possible for any network with availability greater than 0.25. We also prove that the problem of calculating A is #P-complete and describe a method for approximating the optimal location for a single copy which adjusts dynamically to current network characteristics. The bound presented here is most useful for high availabilities, which tend to be obtainable with modern networks and their constituent sites and links.

A fundamental problem of distributed system design in an existing network where components can fail is finding an optimal location at which to place a resource. This paper proves exactly how hard this placement problem is under the measure of data availability. Specifically, it shows that the optimal placement problem for availability is #P-complete, a measure of intractability at least as severe as $NP$-completeness. To obtain these results, the environment in which a distributed system operates is modelled by a probabilistic graph, which is a set of fully reliable vertices representing sites and a set of edges representing communication links, each operational with a rational probability. Finding the optimal placement in a probabilistic graph is proved to be #P-complete by giving a sequence of Turing reductions from #Satisfiability. This result is generalized to networks in which each site and each link has an independent, rational operational probability and to networks in which all the sites or all the links have fixed, uniform operational probabilities. Given the anticipated computational difficulty of finding an exact solution, the requirements for effective, practical approximation methods are discussed.

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph G = (V;E) of n = jV j vertices andm = jEj edges on an EREW PRAM in O(log3=2n) time using n+m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.

Computing the connected components of an undirected graph G=(V, E) on mod V mod =n vertices and mod E mod =m edges is addressed. An efficient and simple algorithm that runs in O(lg/sup 3/2/ n) time using n+m CREW processors is presented.>

We present an upper bound on the performance provided by a protocol guaranteeing mutually exclusive access to a replicated resource in a network subject to component failure and subsequent partitioning.The bound is presented in terms of the performance of a single resource in the same network.The bound is tight and is the first such bound known to us.Since mutual exclusion is one of the requirements for maintaining the consistency of a database object, this bound provides an upper limit on the availability provided by any database consistency control protocol, including those employing dynamic data relocation and replication.We show that if a single copy provides availability A for O < A < 1, then no scheme can achieve availabdity greater than ~ in the same network.We show this bound to be the best possible for any network with availabdit y greater than .25.Although, as we prove, the problem of calculating A is #Pcompletej we describe a method for approximating the op timal location for a single copy which adjusts dynamically to current network characteristics.This bound is most useful for high availabilities, which tend to be obtainable with modern networks and their constituent sites and links.

Previous article Full AccessErratum: Generalized Selection and Ranking: Sorted MatricesGreg N. Frederickson and Donald B. JohnsonGreg N. Frederickson and Donald B. Johnsonhttps://doi.org/10.1137/0219013PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: Generalized Selection and Ranking: Sorted Matrices." SIAM Journal on Computing, 19(1), pp. 205–206[1] Greg N. Frederickson and , Donald B. Johnson, Generalized selection and ranking: sorted matrices, SIAM J. Comput., 13 (1984), 14–30 10.1137/0213002 85c:68025 LinkISIGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Scheduling with gaps: new models and algorithms21 July 2021 | Journal of Scheduling, Vol. 24, No. 4 Cross Ref Geometric clusteringACM Transactions on Algorithms, Vol. 7, No. 4 Cross Ref Cache-oblivious selection in sorted matricesInformation Processing Letters, Vol. 109, No. 2 Cross Ref Volume 19, Issue 1| 1990SIAM Journal on Computing History Submitted:10 October 1989Accepted:16 October 1989Published online:31 July 2006 InformationCopyright © 1990 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0219013Article page range:pp. 205-206ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Algorithms are given that compute maximum flows in planar directed networks either in O ((log n ) 3 ) parallel time using O ( n 4 ) processors or O ((log n ) 2 ) parallel time using O ( n 6 ) processors. The resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. When such a value is given, or when the computation is on an undirected network, the bound is O ((log n ) 2 ) time using O ( n 3 ) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.

It is shown how to extend the techniques originally used to prove a lower bound of Ω( n 2 ) for the product of the time and space consumed for sorting in branching programs with elementary comparisons, to the case of linear branching programs where linear functions on n input elements can be computed in unit time.

A new algorithm is given to find a maximum flow in an undirected planar flow network in $O(n\log ^2 n)$ time, which is faster than the best method previously known by a factor of $\sqrt n /\log n$. The algorithm constructs a transformation of the dual of the given flow network in which differences between shortest distances are equal, under suitable edge correspondences, to edge flows in the given network. The transformation depends on the value of a maximum flow. The algorithm then solves the shortest distances problem efficiently by exploiting certain structural properties of the transformed dual, as well as using a set of cuts constructible in $O(n\log ^2 n)$ time by a known method which is also used to find the requisite flow value. The main result can be further improved by a factor of $\log n/\log^* n$ if a recently developed shortest path algorithm for planar networks is used in place of Dijkstra’s algorithm in each step where shortest paths are computed.

A more general version of the well-known selection problem is formulated, in which constraints on the input set are allowed. Selection (and also ranking) problems are solved optimally for the broad class of inputs constrained to be collections of matrices with sorted rows and sorted columns.The characterization of problem complexity includes an asymptotically significant dependency on the rank of the solution element.

We give a new characterization of the planar separator theorem in terms of mutually non-containing closed Jordan Curves. using this, we develop an O(n √n logn) maximum flow algorithm for directed planar networks (hence for any planar network).

Algorithms are given that compute maximum flows in planar directed networks either in O((logn)3) parallel time using O(n4) processors or O((logn)2) parallel time using O(n6) processors. The resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. When such a value is given, or when the computation is on an undirected network, the bound is O((logn)2) time using O(n4) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.

Selection in a set requires time linear in the size of the set when there are no a priori constraints on the total orders possible for the set. Constraints often come for free, however, with sets which arise in applications. Linear time selection [Bl] can be suboptimal for such problems. We therefore generalize the well known selection problem to admit constraints on the input sets, with a view toward settling the complexity issues which arise. The generalization also applies to the other quantile problems of ranking a given element in the input set and verification of the claim that a given element has a specified rank.

An algorithm which schedules forests of n tasks on m identical processors in O ( n log m ) time, offline, is given. The schedules are optimal with respect to finish time and contain at most n - 2 preemptions, a bound which is realized for all n . Also given is a simpler algorithm which runs in O ( nm ) time on the same problem and can be adapted to give optimal finish time schedules on-line for independent tasks with release times.

The graph-theoretical models of this paper can be used to compare the rounding error behavior of numerical programs The models follow the approach, popularized by Wilkinson, of assuming independent rounding errors at each arithmetic operation Models constructed on th~s assumpuon are more tractable than would be the case under more realistic assumptions There are identified two easily tested condmons on programs which guarantee that" error analyses are relatively lnsensmve to the particular graph model employed The development has the addmonal benefit of sometimes providing an elementary proof that one program is comparable in stablhty to another Examples of such results are gwen KEY WORDS AND PHRASES rounding errors, numerical stability, arithmetic graphs CR CATEGORIES 5 11, 5 14In order to represent programs as "arithmetic graphs," we restrict attention to straight-

article Free Access Share on Lower Bounds for Selection in X + Y and Other Multisets Authors: Donald B. Johnson Computer Science Department, The Pennsylvania State University, University Park, PA Computer Science Department, The Pennsylvania State University, University Park, PAView Profile , Samuel D. Kashdan Computer Science Department, The Pennsylvania State University, University Park, PA Computer Science Department, The Pennsylvania State University, University Park, PAView Profile Authors Info & Claims Journal of the ACMVolume 25Issue 4Oct. 1978 pp 556–570https://doi.org/10.1145/322092.322097Online:01 October 1978Publication History 24citation671DownloadsMetricsTotal Citations24Total Downloads671Last 12 Months12Last 6 weeks2 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An algorithm is given which selects the Kth element in $X + Y$ in $O(n\log n)$ time and $O(n)$ space, where $X + Y$ is the multiset $\{ x_i + y_j | x_i \in X\text{ and } y_j \in Y\} $ for $X = (x_1 ,x_2 , \cdots ,x_n )$ and $Y = (y_1 ,y_2 , \cdots ,y_n )$, n-tuples of real numbers. The results are extended to $\sum_{i = 1}^m {X_i } $ for $m > 2$. There is strong evidence that this more general problem is difficult if m and K may be selected arbitrarily. However, algorithms can be shown which are fast for small K and arbitrary m.

Algorithms for finding shortest paths are presented which are faster than algorithms previously known on networks which are relatively sparse in arcs. Known results which the results of this paper extend are surveyed briefly and analyzed. A new implementation for priority queues is employed, and a class of “arc set partition” algorithms is introduced. For the single source problem on networks with nonnegative arcs a running time of O (min( n 1+1/ k + e , n + e ) log n )) is achieved, where there are n nodes and e arcs, and k is a fixed integer satisfying k > 0. This bound is O ( e ) on dense networks. For the single source and all pairs problem on unrestricted networks the running time is O (min( n 2+1/ k + ne , n 2 log n + ne log n ).

An algorithm is presented which finds all the elementary circuits of a directed graph in time bounded by $O((n + e)(c + 1))$ and space bounded by $O(n + e)$, where there are n vertices, e edges and c elementary circuits in the graph. The algorithm resembles algorithms by Tiernan and Tarjan, but is faster because it considers each edge at most twice between any one circuit and the next in the output sequence.

An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O ( n 3 ) steps is disproved by showing a set of networks which take O ( n 2 n ) steps.