Computing dominators in parallel

DOI10.1016/0020-0190(87)90136-0zbMATH Open0653.68067OpenAlexW1988075678MaRDI QIDQ1108035FDOQ1108035

Authors: Shaunak R. Pawagi, P. S. Gopalakrishnan, I. V. Ramakrishnan 

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90136-0

Recommendations

• Computing dominators on a cube-connected machine
• Finding dominators via disjoint set union
• Efficient parallel algorithms for path problems in directed graphs
• Algorithms – ESA 2004
• Finding Dominators in Practice

zbMATH Keywords

parallel algorithmtransitive closuretime complexitydominatorsparallel random access machinedirected acylic graphprocessor complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Parallel computation and conflicts in memory access
• On the Asymptotic Complexity of Matrix Multiplication
• Title not available (Why is that?)
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• The theory of languages

Cited In (8)

• Computing dominators on a cube-connected machine
• Efficient Computation of Dominance in Component Systems (Short Paper)
• Finding Dominators in Practice
• A uniform approach to semi-dynamic problems on digraphs
• Dag-calculus: a calculus for parallel computation
• Efficient parallel algorithms for path problems in directed graphs
• Computing Frequency Dominators and Related Problems
• Counting edges in a dag

This page was built for publication: Computing dominators in parallel

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