A parallel algorithm for eliminating cycles in undirected graphs

DOI10.1016/0020-0190(90)90015-PMaRDI QIDQ910243zbMATH OpenFDO

Authors Clifford Stein, Philip N. Klein

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmcyclesundirected graphsEuler tourCRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Parallel algorithms for connectivity problems in graph theory
• A parallel algorithm for the maximal path problem
• Publication:4489037
• Finding fundamental cycles and bridges on a tree-structured parallel computer
• Parallel algorithms for maximal acyclic sets

Cites work

• scientific article; zbMATH DE number 4064467 (Why is no real title available?)
• scientific article; zbMATH DE number 4064468 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• An O(logn) parallel connectivity algorithm
• Matching is as easy as matrix inversion
• Scaling algorithms for network problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(10)

• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• A parallel algorithm for the maximum 2-chain edge packing problem
• scientific article; zbMATH DE number 2089184 (Why is no real title available?)
• A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph
• Cooperative Distributed Algorithms for Dynamic Cycle Prevention
• An optimal PRAM algorithm for a spanning tree on trapezoid graphs.
• Finding Euler tours in parallel
• A parallel algorithm for approximating the minimum cycle cover
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs
• scientific article; zbMATH DE number 1534586 (Why is no real title available?)

This page was built for publication: A parallel algorithm for eliminating cycles in undirected graphs

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