Finding Euler tours in parallel

DOI10.1016/0022-0000(84)90003-5zbMath0552.68060MaRDI 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 computation; parallel algorithms; Euler tours; concurrent-read concurrent-write parallel RAM; Euler graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

68N25: Theory of operating systems

68W99: Algorithms in computer science

Related Items

THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, 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, Efficient parallel algorithms for path problems in directed graphs, Constructing the Voronoi diagram of a set of line segments in parallel, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Efficient algorithms for path partitions, An optimal parallel algorithm for planar cycle separators, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, On Trade-Offs in External-Memory Diameter-Approximation

Cites Work

• 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
• Unnamed Item