Parallel ear decomposition search (EDS) and st-numbering in graphs
From MaRDI portal
Publication:1095666
DOI10.1016/0304-3975(86)90153-2zbMath0632.68066OpenAlexW2061303458WikidataQ61772232 ScholiaQ61772232MaRDI QIDQ1095666
Uzi Vishkin, Baruch Schieber, Yael Maon
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90153-2
Related Items
The complexity of planarity testing, Planarity testing in parallel, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, Data-Oblivious Graph Algorithms in Outsourced External Memory, Successive approximation in parallel graph algorithms, Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm, Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions, A new graph triconnectivity algorithm and its parallelization, Algorithms for computing a parameterized \(st\)-orientation, Parallel search algorithms for graphs and trees, Balanced vertex-orderings of graphs, Successive approximation in parallel graph algorithms, Design and Engineering of External Memory Traversal Algorithms for General Graphs, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, Optimal \(st\)-orientations for plane triangulations, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Bipolar orientations revisited, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sorting in \(c \log n\) parallel steps
- On efficient parallel strong orientation
- Computing an st-numbering
- The VLSI Complexity of Sorting
- An Efficient Parallel Biconnectivity Algorithm
- Parallel Prefix Computation
- Parallel Algorithms in Graph Theory: Planarity Testing
- An O(logn) parallel connectivity algorithm
