Some triply-logarithmic parallel algorithms
Omer Berkman, Joseph F. JáJá, Sridhar Krishnamurthy, Ramakrishna Thurimella, Uzi Vishkin · 2002
It is established that several natural problems have triply logarithmic, or even faster, optimal parallel algorithms. These problems include: merging two sorted lists, where the values are drawn from a large, but restricted, domain on a CREW PRAM; finding all prefix minima, where the values are drawn from a restricted domain; and top-bottom global routing around a rectangle, a well-investigated problem in VLSI routing for which only highly involved serial algorithms were known.>