Finding Euler tours in parallel

DOI10.1016/0022-0000(84)90003-5zbMATH Open0552.68060OpenAlexW4210697874MaRDI QIDQ801686FDOQ801686

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

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

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)

Cites Work

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

Cited In (15)

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

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)