TY - CHAP AU - Lürwer-Brüggemeier, Katharina AU - Meyer auf der Heide, Friedhelm ID - 16732 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Capabilities and complexity of computations with integer division ER - TY - JOUR AB - We consider the following periodic sorting procedure on two-dimensional meshes of processors: Initially, each node contains one number. We proceed in rounds each round consisting of sorting the columns of the grid, and, in the second phase, of sorting the rows according to the snake-like ordering. We exactly characterize the number of rounds necessary to sort on an l × m-grid in the worst case, where l is the number of the rows and m the number of the columns. An upper bound of ⌈ log l⌉ + 1was known before. This bound is tight for the case that m is not a power of 2. Surprisingly, it turns out that far fewer rounds are necessary if m is a power of 2 (and m ≪ l) in this case, exactly min { log m + 1, ⌈ log l⌉ + 1} rounds are needed in the worst case. AU - Kutylowski, Miroslaw AU - Wanka, Rolf ID - 18936 JF - Parallel Processing Letters 2 SN - 0129-6264 TI - Periodic Sorting on Two-Dimensional Meshes ER - TY - CHAP AU - Dietzfelbinger, Martin AU - Meyer auf der Heide, Friedhelm ID - 16733 SN - 0302-9743 T2 - Data structures and efficient algorithms TI - High performance universal hashing, with applications to shared memory simulations ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16734 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Hashing strategies for simulating shared memory on distributed memory machines ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Pham, Hieu Thien ID - 16735 SN - 0302-9743 T2 - STACS 92 TI - On the performance of networks with multiple busses ER - TY - CONF AU - Karp, Richard M. AU - Luby, Michael AU - Meyer auf der Heide, Friedhelm ID - 16736 SN - 0897915119 T2 - Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 TI - Efficient PRAM simulation on a distributed memory machine ER - TY - CHAP AU - Dietzfelbinger, Martin AU - Meyer auf der Heide, Friedhelm ID - 16737 SN - 1615-4584 T2 - TEUBNER-TEXTE zur Informatik TI - Dynamic Hashing in Real Time ER - TY - CHAP AU - Alt, Helmut AU - Blömer, Johannes AU - Wagener, Hubert ID - 3050 SN - 3540528261 T2 - Automata, Languages and Programming TI - Approximation of convex polygons ER - TY - CHAP AU - Dietzfelbinger, Martin AU - Meyer auf der Heide, Friedhelm ID - 16738 SN - 3540528261 T2 - Automata, Languages and Programming TI - A new universal class of hash functions and dynamic hashing in real time ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16739 SN - 3540529535 T2 - Lecture Notes in Computer Science TI - Dynamic hashing strategies ER - TY - CHAP AU - Karpinski, Marek AU - Meyer auf der Heide, Friedhelm ID - 16740 SN - 3540529535 T2 - Lecture Notes in Computer Science TI - On the complexity of genuinely polynomial computation ER - TY - CONF AU - Dietzfelbinger, M. AU - Meyer auf der Heide, Friedhelm ID - 16741 SN - 0897913612 T2 - Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 TI - How to distribute a dictionary in a complete network ER - TY - CONF AU - Gil, J. AU - Meyer auf der Heide, Friedhelm AU - Wigderson, A. ID - 16742 SN - 0897913612 T2 - Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 TI - Not all keys can be hashed in constant time ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16824 IS - 4 JF - Informatik Spektrum TI - Das Heinz Nixdorf-Institut der Universität-GH Paderborn VL - 13 ER - TY - JOUR AU - Just, Bettina AU - Meyer auf der Heide, Friedhelm AU - Wigderson, Avi ID - 16743 JF - RAIRO - Theoretical Informatics and Applications SN - 0988-3754 TI - On computations with integer division ER - TY - CONF AU - Dietzfelbinger, M. AU - Meyer auf der Heide, Friedhelm ID - 16744 SN - 089791323X T2 - Proceedings of the first annual ACM symposium on Parallel algorithms and architectures - SPAA '89 TI - An optimal parallel dictionary ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16745 SN - 3540508406 T2 - STACS 89 TI - On genuinely time bounded computations ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Wanka, Rolf ID - 16746 SN - 3540508406 T2 - STACS 89 TI - Time-optimal simulations of networks by universal parallel computers ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16789 SN - 0302-9743 T2 - STACS 89 TI - Computing minimum spanning forests on 1- and 2-dimensional processor arrays ER - TY - JOUR AU - Babai, László AU - Just, Bettina AU - Meyer auf der Heide, Friedhelm ID - 16763 JF - Information and Computation SN - 0890-5401 TI - On the limits of computations with the floor function ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16764 JF - Journal of the ACM (JACM) SN - 0004-5411 TI - Fast algorithms for N-dimensional restrictions of hard problems ER - TY - JOUR AU - Borodin, Allan AU - Fich, Faith E. AU - Meyer auf der Heide, Friedhelm AU - Upfal, Eli AU - Wigderson, Avi ID - 16765 JF - Theoretical Computer Science SN - 0304-3975 TI - A tradeoff between search and update time for the implicit dictionary problem ER - TY - CONF AU - Dietzfelbinger, M. AU - Karlin, A. AU - Mehlhorn, K. AU - Meyer auf der Heide, Friedhelm AU - Rohnert, H. AU - Tarjan, R.E. ID - 16766 SN - 0818608773 T2 - [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science TI - Dynamic perfect hashing: upper and lower bounds ER - TY - CHAP AU - Just, Bettina AU - Mathematik, Fb AU - Meyer auf der Heide, Friedhelm AU - Informatik, Fb AU - Wigderson, Avi ID - 16767 SN - 0302-9743 T2 - STACS 88 TI - On computations with integer division ER - TY - CHAP AU - Dietzfelbinger, M. AU - Mehlhorn, K. AU - Meyer auf der Heide, Friedhelm AU - Rohnert, H. ID - 16768 SN - 0302-9743 T2 - SWAT 88 TI - Upper and lower bounds for the dictionary problem ER - TY - JOUR AU - Borodin, A. AU - Fich, F. AU - Meyer auf der Heide, Friedhelm AU - Upfal, E. AU - Wigderson, A. ID - 16772 JF - SIAM Journal on Computing SN - 0097-5397 TI - A Time-Space Tradeoff for Element Distinctness ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Wigderson, Avi ID - 16773 JF - SIAM Journal on Computing SN - 0097-5397 TI - The Complexity of Parallel Sorting ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16771 JF - SIAM Journal on Computing SN - 0097-5397 TI - Efficient Simulations among Several Models of Parallel Computers ER - TY - CHAP AU - Borodin, Allan AU - Fich, Faith E. AU - Meyer auf der Heide, Friedhelm AU - Upfal, Eli AU - Wigderson, Avi ID - 16774 SN - 0302-9743 T2 - Automata, Languages and Programming TI - A tradeoff between search and update time for the implicit dictionary problem ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16775 SN - 0302-9743 T2 - STACS 86 TI - Speeding up random access machines by few processors ER - TY - CHAP AU - Borodin, A. AU - Fich, F. AU - Meyer auf der Heide, Friedhelm AU - Upfal, E. AU - Wigderson, A. ID - 16776 SN - 0302-9743 T2 - STACS 86 TI - A time-space tradeoff for element distinctness ER - TY - JOUR AU - Lautemann, Clemens AU - Meyer auf der Heide, Friedhelm ID - 16779 JF - Information Processing Letters SN - 0020-0190 TI - Lower time bounds for integer programming with two variables ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16780 JF - Journal of the ACM (JACM) SN - 0004-5411 TI - Lower bounds for solving linear diophantine equations on random access machines ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16781 JF - Theoretical Computer Science SN - 0304-3975 TI - Simulating probabilistic by deterministic algebraic computation trees ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Wigderson, Avi ID - 16782 SN - 0818606444 T2 - 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) TI - The complexity of parallel sorting ER - TY - CONF AU - Fich, F E AU - Meyer auf der Heide, Friedhelm AU - Ragde, P AU - Wigderson, A ID - 16783 SN - 0897911512 T2 - Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 TI - One, two, three . . . infinity: lower bounds for parallel computation ER - TY - CONF AU - Meyer auf der Heide, Friedhelm ID - 16784 SN - 0897911512 T2 - Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 TI - Fast algorithms for n-dimensional restrictions of hard problems ER - TY - CONF AU - Meyer auf der Heide, Friedhelm ID - 16788 SN - 0818606444 T2 - 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) TI - Nondeterministic versus probabilistic linear search algorithms ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16823 IS - 1-3 JF - Information and Control TI - Lower time bounds for solving linear diophantine equations on several parallel computational models VL - 67 ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16785 JF - Journal of the ACM (JACM) SN - 0004-5411 TI - A Polynomial Linear Search Algorithm forr the n-Dimensional Knapsack Problem ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Reischuk, R. ID - 16786 SN - 081860591X T2 - 25th Annual Symposium onFoundations of Computer Science, 1984. TI - On The Limits To Speed Up Parallel Machines By Large Hardware And Unbounded Communication ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16787 SN - 0302-9743 T2 - STACS 84 TI - Efficient simulations among several models of parallel computers (extended abstract) ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16806 JF - Acta Informatica SN - 0001-5903 TI - Efficiency of universal parallel computers ER - TY - JOUR AU - Klein, Peter AU - Meyer auf der Heide, Friedhelm ID - 16807 JF - Acta Informatica SN - 0001-5903 TI - A lower time bound for the knapsack problem on random access machines ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16808 JF - Information Processing Letters SN - 0020-0190 TI - Infinite cube-connected cycles ER - TY - CONF AU - Meyer auf der Heide, Friedhelm ID - 16809 SN - 0897910990 T2 - Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 TI - A polynomial linear search algorithm for the n-dimensional knapsack problem ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16810 SN - 3540119736 T2 - Lecture Notes in Computer Science TI - Efficiency of universal parallel computers ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Rollik, Anton ID - 16813 SN - 0302-9743 T2 - Fundamentals of Computation Theory TI - Random access machines and straight-line programs ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm ID - 16814 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Time-processor trade-offs for universal parallel computers ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16820 JF - Theoretical Computer Science SN - 0304-3975 TI - A comparison of two variations of a pebble game on graphs ER - TY - CHAP AU - Klein, P. AU - Meyer auf der Heide, Friedhelm ID - 16815 SN - 0343-3005 T2 - GI - 10. Jahrestagung TI - Untere Zeitschranken für das Rucksack-Problem ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm ID - 16812 JF - Automata, Languages and Programming. ICALP 1979 TI - A comparison of two variations of a pebble game on graphs ER -