A parallel algorithm for eliminating cycles in undirected graphs

DOI10.1016/0020-0190(90)90015-PzbMath0695.68051MaRDI QIDQ910243

Clifford Stein, Philip N. Klein

Publication date: 1990

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

zbMATH Keywords

cyclesparallel algorithmundirected 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)

Related Items

An optimal PRAM algorithm for a spanning tree on trapezoid graphs., An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs, A parallel algorithm for approximating the minimum cycle cover, An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scaling algorithms for network problems
• Matching is as easy as matrix inversion
• An O(logn) parallel connectivity algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems