Finding Euler tours in parallel

DOI10.1016/0022-0000(84)90003-5MaRDI QIDQ801686zbMATHOpenAlexFDO

Authors 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) Algorithms in computer science (68W99) Theory of operating systems (68N25)

Recommendations

• Exact counting of Euler tours for generalized series-parallel graphs
• A parallel algorithm for eliminating cycles in undirected graphs
• Parallel algorithms for connectivity problems in graph theory
• scientific article; zbMATH DE number 3946164
• scientific article; zbMATH DE number 3905859

Cites work

• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• An Efficient Parallel Biconnectivity Algorithm
• An O(logn) parallel connectivity algorithm
• Implementation of simultaneous memory address access in models that forbid it
• Sorting in \(c \log n\) parallel steps
• The VLSI Complexity of Sorting

Cited in

(15)

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

This page was built for publication: Finding Euler tours in parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q801686)