Efficient parallel triconnectivity in logarithmic time
Lecture notes in computer sciencePublished 1 January 1988
Vijaya Ramachandran, Uzi Vishkin
Citations37
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two new techniques for trimming a logarithmic factor from the running time of efficient parallel algorithms for graph problems are presented, leading to an improvement in running time from O (log2 n) to O(logn) for efficient triconnectivity testing in parallel.
Abstract
We present two new techniques for trimming a logarithmic factor from the running time of efficient parallel algorithms for graph problems. The main application of our techniques is an improvement in running time from O (log2 n) to O(logn) for efficient triconnectivity testing in parallel. Additional applications include almost optimal O(logn) time algorithms for recognizing Gauss codes, for testing planarity of graphs with a known Hamiltonian cycle and for testing if a permutation is sortable on two stacks.
Keywords
Computer Science
Graph Algorithms
1,284 Citations1979Shimon Even
A thoroughly revised second edition of Shimon Even's Graph Algorithms, with a foreword by Richard M. Karp and notes by Andrew V Goldberg, explains algorithms in a formal but simple language with a direct and intuitive presentation.
Journal of AlgorithmsAn O(logn) parallel connectivity algorithm
598 Citations1982Yossi Shiloach, Uzi Vishkin
It is conjectured that the barrier of O(log n) cannot be surpassed by any polynomial number of processors and that this performance cannot be achieved in the weaker model.
Transactions of the American Mathematical SocietyNon-separable and planar graphs
501 Citations1932Hassler Whitney
Communications of the ACMComputing connected components on parallel computers
267 Citations1979D. S. Hirschberg, Ashok K. Chandra +1 more
A parallel algorithm which uses n=2 processors to find the connected components of an undirected graph with n vertices in time in time O(n), which can be used to finding the transitive closure of a symmetric Boolean matrix.
Approximate and exact parallel scheduling with applications to list, tree and graph problems
176 Citations1986Richard Cole, Uzi Vishkin
A novel scheduling problem is defined; it is solved by repeated, rapid, approximate reschedulings, which leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time.
Elsevier eBooksQUEUES, STACKS AND GRAPHS
157 Citations1971Shimon Even, Alon Itai
An alternative way of defining a union graph as the graph describing the intersection of chords in a circle is shown, in spite of the fact that the set of all union graphs is a proper subset of all graphs, no efficient algorithm to color them has yet been found.
Theoretical Computer ScienceParallel ear decomposition search (EDS) and st-numbering in graphs
114 Citations1986Yael Maon, Baruch Schieber +1 more
A general method for searching efficiently in parallel undirected graphs, called ear-decomposition search (EDS), based on depth-first search (DFS), is presented.
A new graphy triconnectivity algorithm and its parallelization
76 Citations1987Gary L. Miller, Vijaya Ramachandran
This work presents a new algorithm for finding the tri-connected components of an undirected graph based on ear decomposition and has linear sequential running time, and is the first efficient parallel algorithm for graph tri-connectivity.
Transactions of the American Mathematical SocietyNon-Separable and Planar Graphs
64 Citations1932Hassler Whitney
Journal of Computer and System SciencesFinding Euler tours in parallel
60 Citations1984Mikhail J. Atallah, Uzi Vishkin
O (log | V |) time algorithms are given using a linear number of processors on a concurrent-read concurrent-write parallel RAM to solve the problem of finding Euler tours in directed and undirected Euler graphs.
Bulletin of the American Mathematical SocietyA forbidden substructure characterization of Gauss codes
47 Citations1976László Lovász, Morris L. Marx
Journal of AlgorithmsGauss codes, planar hamiltonian graphs, and stack-sortable permutations
35 Citations1984Pierre Rosenstiehl, Robert E. Tarjan
A simple linear-time algorithm that solves all three recognition problems and is previously used in general planarity testing, called a pile of twin stacks is described.
arXiv (Cornell University)Optimal Preprocessing for Answering On-Line Product Queries
28 Citations2024Ilan Alon, Baruch Schieber
The amount of preprocessing needed for answering certain on-line queries as fast as possible is examined, and sequential preprocessing algorithms can be parallelized efficiently to give optimal parallel algorithms which run in $O(\log n)$ time on a CREW PRAM.