New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
From MaRDI portal
Publication:4720785
DOI10.1109/TC.1986.1676783zbMath0613.68023MaRDI QIDQ4720785
Jeffrey Scott Vitter, Roger A. Simons
Publication date: 1986
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
parallel algorithms; unification; PRAM; depth-first search; union-find; random access; RAM; WRAM; fifth generation; monotone circuit value; path system accessibility
Related Items
THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Efficient parallel term matching and anti-unification, Unifications, deunifications, and their complexity, A sublinear parallel algorithm for some dynamic programming problems, Deciding bisimilarity is P-complete, A theory of strict P-completeness, Local consistency in parallel constraint satisfaction networks, Graph coloring on coarse grained multicomputers, Data independence of read, write, and control structures in PRAM computations, Parallel computation of manipulator inverse dynamics