We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n 1/2 ) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs.

Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed graphs, including breadth-first search, topological sort, strong connectivity, and and the single source shorest path problem. All of the algorithms run on the EREW PRAM model of parallel computer, except the algorithm for strong connectivity, which runs on the probabilistic EREW PRAM.

We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions and that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs.

Article Free Access Share on Separator based sparsification for dynamic planar graph algorithms Authors: David Eppstein View Profile , Zvi Galil View Profile , Giuseppe F. Italiano View Profile , Thomas H. Spencer View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 208–217https://doi.org/10.1145/167088.167159Published:01 June 1993Publication History 23citation582DownloadsMetricsTotal Citations23Total Downloads582Last 12 Months25Last 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 AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Every graph with n vertices and m edges has an independent set containing at least $n^2 / (2m + n)$ vertices. This paper presents a parallel algorithm that finds an independent set of this size and runs in $O( \log^3 n )$ time on a CROW PRAM with $O( ( m + n)\alpha ( m,n )/ \log^2 n)$ processors, where $\alpha ( n,m )$ is a functional inverse of Ackerman’s function. The ideas used in the design of this algorithm are also used to design an algorithm that, with the same resources, finds a vertex coloring satisfying certain minimality conditions.

Article Free Access Share on More time-work tradeoffs for parallel graph algorithms Author: Thomas H. Spencer Computer Science Department, Rensselaer Polytechnic Institute Computer Science Department, Rensselaer Polytechnic InstituteView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 81–93https://doi.org/10.1145/113379.113387Published:01 June 1991Publication History 12citation301DownloadsMetricsTotal Citations12Total Downloads301Last 12 Months8Last 6 weeks1 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

The ( component ) merging problem is a new graph problem. Versions of this problem appear as bottlenecks in various graph algorithms. A new data structure solves this problem efficiently, and two special cases of the problem have even more efficient solutions based on other data structures. The performance of the data structures is sped up by introducing a new algorithmic tool called packets . The algorithms that use these solutions to the component merging problem also exploit new properties of two existing data structures. Specifically, Β-trees can be used simultaneously as a priority queue and a concatenable queue. Similarly, F-heaps support some kinds of split operations with no loss of efficiency. An immediate application of the solution to the simplest version of the merging problem is an Ο( t ( m , n )) algorithm for finding minimum spanning trees in undirected graphs without using F-heaps, where t ( m , n ) = m log 2 log 2 log d n , the graph has n vertices and m edges, and d = max( m / n , 2). Packets also improve the F-heap minimum spanning tree algorithm, giving the fastest algorithm currently known for this problem. The efficient solutions to the merging problem and the new observation about F-heaps lead to an Ο( n ( t ( m , n ) + n log n )) algorithm for finding a maximum weighted matching in general graphs. This settles an open problem posed by Tarjan [ 15, p. 123], where the weaker bound of O ( nm log ( n 2 / m )) was conjectured.

A new parallel algorithm for the maximal independent set problem is constructed. It runs in $O(\log ^4 n)$ time when implemented on a linear number of EREW-processors. This is the first deterministic algorithm for the maximal independent set problem (MIS) whose running time is polylogarithmic and whose processor-time product is optimal up to a polylogarithmic factor.

The problem of constructing in parallel a maximal independent set of a given graph is considered. A new deterministic NC-algorithm implemented in the EREW PRAM model is presented. On graphs with n vertices and m edges, it uses $O((n + m)/\log n)$ processors and runs in $O(\log^3 n)$ time. This reduces by a factor of $\log n$ both the running time and the processor count of the previously fastest deterministic algorithm that solves the problem using a linear number of processors.

A new parallel algorithm for the maximal independent set problem (MIS) is constructed. It runs in O(log4 n) time when implemented on a linear number of EREW-processors. This is the first deterministic algorithm for MIS whose running time is polylogarithmic and whose processor-time product is optimal up to a polylogarithmic factor.

This correspondence addresses actual implementation of a multiway fan-out and its effect on test generation. If a test generation ignores the fan-out implementation faults may be left undetected by the test set. Moreover, different implementations of the multiway fan-out may lead to different fault coverages. Careless implementation of the fan-out may also yield undetectable faults. Some guidelines for fan-out implementation that may enhance testability are given in this correspondence.

We define a graph problem which we refer to as the component merging problem. Versions of the problem appear as bottlenecks in various graph algorithms. We show how to solve an important special case of the problem.