Finding Euler tours in parallel

DOI10.1016/0022-0000(84)90003-5zbMath0552.68060OpenAlexW4210697874MaRDI QIDQ801686

Mikhail J. Atallah, Uzi Vishkin

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90003-5

zbMATH Keywords

parallel computationparallel algorithmsEuler toursconcurrent-read concurrent-write parallel RAMEuler graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Theory of operating systems (68N25) Algorithms in computer science (68W99)

Related Items

Improved parallel depth-first search in undirected planar graphs, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, An optimal parallel algorithm for planar cycle separators, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, A parallel algorithm for the maximum 2-chain edge packing problem, A one pass streaming algorithm for finding Euler tours, On Trade-Offs in External-Memory Diameter-Approximation, Efficient parallel algorithms for path problems in directed graphs, Constructing the Voronoi diagram of a set of line segments in parallel, Efficient algorithms for path partitions, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS

Cites Work

• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• The VLSI Complexity of Sorting
• An Efficient Parallel Biconnectivity Algorithm
• An O(logn) parallel connectivity algorithm
• Implementation of simultaneous memory address access in models that forbid it