Computing dominators in parallel

DOI10.1016/0020-0190(87)90136-0MaRDI QIDQ1108035zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• On the Asymptotic Complexity of Matrix Multiplication
• Parallel computation and conflicts in memory access
• 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
• Efficient parallel algorithms for path problems in directed graphs
• Dag-calculus: a calculus for parallel computation
• 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)