Secondly, we show how to count all star-shaped polygons whose vertices are a subset of ( S ) in ( O(n^5log n) ) time and ( O(n) ) space. The algorithm can also be used for random uniform generation. We also present lower and upper bounds on the number of star-shaped polygons. AU - Sohler, Christian ID - 18576 T2 - Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99) TI - Generating Random Star-Shaped Polygons ER - TY - CONF AB - We present a new ( O(n) ) algorithm to compute good orders for the point set of a Delaunay triangulation of ( n ) points in the plane. Such a good order makes reconstruction in ( O(n) ) time with a simple algorithm possible. In contrast to the algorithm of Snoeyink and van Kreveld cite1, which is based on independent sets, our algorithm uses a breadth first search (BFS) to obtain these orders. Both approaches construct such orders by repeatedly removing a constant fraction of vertices from the current triangulation. The advantage of the BFS approach is that we can give significantly better bounds on the fraction of removed points in a phase of the algorithm. We can prove that a single phase of our algorithm removes at least ( frac13 ) of the points, even if we restrict the degree of the points (at the time they are removed) to 6. We implemented and compared both algorithms. Our algorithms is slightly faster and achieves about 15% better vertex data compression when using a simple variable length code to encode the differences between two consecutive vertices of the given order. AU - Sohler, Christian ID - 18747 T2 - Proceedings of the 11th Canadian Conference on Computational Geometry ( CCCG'99) TI - Fast Reconstruction of Delaunay Triangulations ER - TY - CONF AU - Berenbrink, Petra AU - Riedel, Marco AU - Scheideler, Christian ID - 2165 T2 - SPAA TI - Simple Competitive Request Scheduling Strategies ER - TY - JOUR AU - Berenbrink, P. AU - Meyer auf der Heide, Friedhelm AU - Schröder, K. ID - 16502 JF - Theory of Computing Systems SN - 1432-4350 TI - Allocating Weighted Jobs in Parallel ER - TY - CONF AU - Scheideler, Christian AU - Vöcking, Berthold ID - 2166 T2 - STOC TI - From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols ER - TY - CONF AU - Krick, Christof AU - Meyer auf der Heide, Friedhelm AU - Räcke, Harald AU - Vöcking, Berthold AU - Westermann, Matthias ID - 18965 SN - 1581131240 T2 - Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA '99 TI - Data management in networks: experimental evaluation of a provably good strategy ER - TY - CHAP AU - Mayr, E. W. AU - Meyer auf der Heide, Friedhelm AU - Wanka, R. ID - 17052 SN - 1431-472X T2 - Informatik aktuell TI - International Workshop on Communication and Data Management in Large Networks ER - TY - CONF AB - We investigate the problem of constructing spanners for a given set of points that are tolerant for edge/vertex faults. Let S be a set of $n$ points in the d-dimensional space and let k be an integer number. A k-edge/vertex fault tolerant spanner for S has the property that after the deletion of k arbitrary edges/vertices each pair of points in the remaining graph is still connected by a short path.

Recently it was shown that for each set S of n points there exists a k-edge/vertex fault tolerant spanner with O(k^2 n) edges which can be constructed in O(n log n + k^2 n) time. Furthermore, it was shown that for each set S of n points there exists a k-edge/vertex fault tolerant spanner whose degree is bouned by O(c^k+1) for some constant c.

Our first contribution is a construction of a k-vertex fault tolerant spanner with O(kn) edges which is a tight bound. The computation takes O(n log^d-1 n + k n log log n) time. Then we show that the same k-vertex fault tolerant spanner is also k-edge fault tolerant. Thereafter, we construct a k-vertex fault tolerant spanner with O(k^2 n) edges whose degree is bounded by O(k^2). Finally, we give a more natural but stronger definition of k-edge fault tolerance which not necessarily can be satisfied if one allows only simple edges between the points of S. We investigate the question whether Steiner points help. We answer this question affirmatively and prove Theta(kn) bounds on the number of Steiner points and on the number of edges in such spanners. AU - Lukovszki, Tamás ID - 18959 SN - 0302-9743 T2 - Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99), LNCS TI - New Results on Fault Tolerant Geometric Spanners ER - TY - THES AU - Lukovszki, Tamás ID - 18942 SN - 3-931466-62-0 TI - New Results on Geometric Spanners and Their Applications ER - TY - JOUR AU - Flammini, Michele AU - Scheideler, Christian ID - 2151 IS - 3 JF - Theory Comput. Syst. TI - Simple, Efficient Routing Schemes for All-Optical Networks VL - 32 ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Martinez, Gabriel Terán ID - 16562 SN - 0302-9743 T2 - LATIN'98: Theoretical Informatics TI - Communication-efficient parallel multiway and approximate minimum cut computation ER - TY - GEN AB - Preis für den Beitrag "Multimediale Entdeckungsreisen unserer Welt mit dem Internet" AU - Ziegler, Martin AU - Fischer, Matthias AU - Lukovszki, Tamás ID - 18145 TI - Multimediale Entdeckungsreisen unserer Welt mit dem Internet ER - TY - CONF AB - New dynamic search data structures developed recently guarantee constant execution time per search and update, i.e., they fulfil the real-time requirements necessary for interactive walkthrough in large geometric scenes. Yet, superiority or even applicability of these new methods in practice was still an open question. Their prototypical implementation presented in this work uses common libraries on standard stations and thus represents a first strut to bridge this gap. Indeed our experimental results give an indication on the actual performance of these theoretical ideas on real machines and possible bottlenecks in future developments. By special algorithmic enhancements, we can even avoid the otherwise essential preprocessing step. AU - Fischer, Matthias AU - Lukovszki, Tamas AU - Ziegler, Martin ID - 17863 T2 - Algorithm Engineering, 2nd International Workshop, {WAE '98} TI - A Network Based Approach for Realtime Walkthrough of Massive Models ER - TY - CONF AU - Adler, Micah AU - Scheideler, Christian ID - 2169 T2 - SPAA TI - Efficient Communication Strategies for Ad-Hoc Wireless Networks (Extended Abstract) ER - TY - CONF AU - Cole, Richard AU - Maggs, Bruce M. AU - Meyer auf der Heide, Friedhelm AU - Mitzenmacher, Michael AU - Richa, Andréa W. AU - Schröder, Klaus AU - Sitaraman, Ramesh K. AU - Vöcking, Berthold ID - 16563 SN - 0897919629 T2 - Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 TI - Randomized protocols for low-congestion circuit routing in multistage interconnection networks ER - TY - THES AU - Oesterdiekhoff, Brigitte ID - 18445 TI - On Periodic Comparator Networks ER - TY - BOOK AU - Scheideler, Christian ID - 2185 SN - 978-3-540-69792-3 TI - Universal Routing Strategies for Interconnection Networks VL - 1390 ER - TY - CHAP AB - We study algorithmic aspects in the management of geometric scenes in interactive walkthrough animations. We consider arbitrarily large scenes consisting of unit size balls. For a smooth navigation in the scene we have to fulfill hard real time requirements. Therefore, we need algorithms whose running time is independent of the total number of objects in the scene and that use as small space as possible. In this work we focus on one of the basic operations in our walkthrough system: reporting the objects around the visitor within a certain distance. Previously a randomized data structure was presented that supports reporting the balls around the visitor in an output sensitive time and allows insertion and deletion of objects nearly as fast as searching. These results were achieved by exploiting the fact that the visitor moves ''slowly'' through the scene. A serious disadvantage of the aforementioned data structure is a big space overhead and the use of randomization. Our first result is a construction of weak spanners that leads to an improvement of the space requirement of the previously known data structures. Then we develop a deterministic data structure for the searching problem in which insertion of objects are allowed. Our incremental data structure supports O(1+k) reporting time, where k is a certain quantity close to the number of reported objects. The insertion time is similar to the reporting time and the space is linear to the total number of objects. AU - Fischer, Matthias AU - Lukovszki, Tamás AU - Ziegler, Martin ID - 17412 SN - 0302-9743 T2 - Algorithms — ESA’ 98 TI - Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time ER - TY - THES AU - Vöcking, Berthold ID - 19639 SN - 3-931466-45-0 TI - Static and Dynamic Data Management in Networks ER - TY - GEN AB - The Paderborn University BSP (PUB) library is a parallel C library based on the BSP model. The basic library supports buffered and unbuffered asynchronous communication between any pair of processors, and a mechanism for synchronizing the processors in a barrier style. In addition, it provides routines for collective communication on arbitrary subsets of processors, partition operations, and a zero-cost synchronization mechanism. Furthermore, some techniques used in the implementation of the PUB library deviate significantly from the techniques used in other BSP libraries. AU - Bonorden, Olaf AU - Rieping, Ingo AU - von Otte, Ingo AU - Juurlink, Bernhardus ID - 19735 TI - The Paderborn University BSP (PUB) Library - Design, Implementation and Performance ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Schröder, Klaus AU - Schwarze, Frank ID - 16503 JF - Theoretical Computer Science SN - 0304-3975 TI - Routing on networks of optical crossbars VL - 196 ER - TY - JOUR AU - Bäumker, Armin AU - Dittrich, Wolfgang AU - Meyer auf der Heide, Friedhelm ID - 16504 JF - Theoretical Computer Science SN - 0304-3975 TI - Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model ER - TY - CONF AU - Feige, Uriel AU - Scheideler, Christian ID - 2170 T2 - STOC TI - Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract) ER - TY - JOUR AU - Scheideler, Christian AU - Vöcking, Berthold ID - 2168 IS - 4 JF - Theory Comput. Syst. TI - Universal Continuous Routing Strategies VL - 31 ER - TY - CHAP AU - Karaivazoglou, Efstratios AU - Meyer auf der Heide, Friedhelm ID - 16687 SN - 0302-9743 T2 - Euro-Par'97 Parallel Processing TI - Routing on asyncronous processor networks ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Storch, M. AU - Wanka, R. ID - 16567 JF - Theory of Computing Systems SN - 1432-4350 TI - Optimal Tradeoffs Between Size and Slowdown for Universal Parallel Networks ER - TY - CONF AU - Sohler, Christian AU - Denny, Markus ID - 18575 T2 - Proceedings of the 9th Canadian Conference on Computational Geometry TI - Encoding a Triangulation as a Permutation of its Point Set ER - TY - GEN AB - In this paper we present a (randomized) algorithm for maintaining the biconnected components of a dynamic planar graph of $n$ vertices under deletions of edges. The biconnected components can be maintained under any sequence of edge deletions in a total of $O(n log n)$ time, with high probability. This gives $O(log n)$ amortized time per edge deletion, which improves previous (deterministic) results due to Giammarresi and Italiano, where $O(n log^2 n)$ amortized time is needed. Our work describes a simplification of the data structures from [GiIt96] and uses dynamic perfect hashing to reduce the running time. As in the paper by Giammarresi and Italiano, we only need $O(n)$ space. Finally we describe some simply additional operations on the decremental data structure. By aid of them this the data structure is applicable for finding efficiently a $Delta$-spanning tree in a biconnected planar graph with a maximum degree $2Delta-2$ do to Czumaj and Strothmann. AU - Strothmann, Willy-Bernhard AU - Lukovszki, Tamás ID - 18955 TI - Decremental Biconnectivity on Planar Graphs ER - TY - THES AU - Dittrich, Wolfgang ID - 19636 SN - 3-931466-26-4 TI - Communication and I/O Efficient Parallel Data Structures ER - TY - THES AU - Bäumker, Armin ID - 19631 SN - 3-931466-27-2 TI - Communication Efficient Parallel Searching ER - TY - CONF AB - Given a connected graph $G$, let a $dT$-spanning tree of $G$ be a spanning tree of $G$ of maximum degree bounded by $dT$. It is well known that for each $dT ge 2$ the problem of deciding whether a connected graph has a $dT$-spanning tree is NP-complete. In this paper we investigate this problem when additionally connectivity and maximum degree of the graph are given. A complete characterization of this problem for 2- and 3-connected graphs, for planar graphs, and for $dT=2$ is provided. Our first result is that given a biconnected graph of maximum degree $2dT-2$, we can find its $dT$-spanning tree in time $O(m+n^3/2)$. For graphs of higher connectivity we design a polynomial-time algorithm that finds a $dT$-spanning tree in any $k$-connected graph of maximum degree $k(dT-2)+2$. On the other hand, we prove that deciding whether a $k$-connected graph of maximum degree $k(dT-2)+3$ has a $dT$-spanning tree is NP-complete, provided $k le 3$. For arbitrary $k ge 3$ we show that verifying whether a $k$-connected graph of maximum degree $k(dT-1)$ has a $dT$-spanning tree is NP-complete. In particular, we prove that the Hamiltonian path (cycle) problem is NP-complete for $k$-connected $k$-regular graphs, if $k>2$. This extends the well known result for $k=3$ and fully characterizes the case $dT=2$. For planar graphs it is NP-complete to decide whether a $k$-connected planar graph of maximum degree $dG$ has a $dT$-spanning tree for $k=1$ and $dG > dT ge 2$, for $k=2$ and $dG > 2(dT-1) ge 2$, and for $k=3$ and $dG > dT = 2$. On the other hand, we show how to find in polynomial (linear or almost linear) time a $dT$-spanning tree for all other parameters of $k$, $dG$, and $dT$. AU - Czumaj, Artur AU - Strothmann, Willy-B. ID - 19869 SN - 0302-9743 T2 - Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97) TI - Bounded degree spanning trees ER - TY - CONF AB - We present a data structure problem which describes the requirements of a simple variant of fully dynamic walk-through animation: We assume the scene to consist of unit size balls in R2 or higher dimensions. The scene may be arbitrarily large and has to be stored in secondary memory (discs) with relatively slow access. We allow a visitor to walk in the scene, and a modeler to update the scene by insertions and deletions of balls. We focus on the realtime requirement of animation systems: For some t (specified by the computation power of (the rendering hardware of) the graphic workstation) the data structure has to guarantee that the balls within distance t of the current visitor's position are presented to the rendering hardware, 20 times per second. Insertions and deletions should also be available to the visitor with small delay, independent of the size of the scene. We present a data structure that fulfills the above task in realtime. Its runtime is output-sensitive, i.e. linear in a quantity close to the output size of the query. We further present (preliminary) experimental results indicating that our structure is efficient in practice. AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm AU - Strothmann, W. -B. ID - 16568 SN - 0302-9743 T2 - 5th Annual European Symposium on Algorithms (ESA '97) TI - Dynamic data structures for realtime management of large geometric scenes VL - 1284 ER - TY - THES AU - Strothmann, Willy-Bernhard ID - 19637 SN - 3-931466-34-5 TI - Bounded Degree Spanning Trees ER - TY - CONF AU - Maggs, B.M. AU - Meyer auf der Heide, Friedhelm AU - Vöcking, B. AU - Westermann, M. ID - 16689 SN - 0818681977 T2 - Proceedings 38th Annual Symposium on Foundations of Computer Science TI - Exploiting locality for data management in systems of limited bandwidth ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Vöcking, Berthold ID - 16569 SN - 0302-9743 T2 - Euro-Par'97 Parallel Processing TI - Static and dynamic data management in networks ER - TY - JOUR AU - Grigoriev, Dima AU - Karpinski, Marek AU - Meyer auf der Heide, Friedhelm AU - Smolensky, Roman ID - 16564 JF - computational complexity SN - 1016-3328 TI - A lower bound for randomized algebraic decision trees ER - TY - JOUR AU - Czumaj, Artur AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 16565 JF - Information and Computation SN - 0890-5401 TI - Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures ER - TY - CONF AU - Berenbrink, Petra AU - Meyer auf der Heide, Friedhelm AU - Schröder, Klaus ID - 16604 SN - 0897918908 T2 - Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures - SPAA '97 TI - Allocating weighted jobs in parallel ER - TY - CONF AU - Flammini, Michele AU - Scheideler, Christian ID - 2179 T2 - SPAA TI - Simple, Efficient Routing Schemes for All-Optical Networks ER - TY - CHAP AU - Bäumker, Armin AU - Meyer auf der Heide, Friedhelm ID - 16605 SN - 0302-9743 T2 - Solving Irregularly Structured Problems in Parallel TI - Communication efficient parallel searching ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Decker, Thomas ID - 16693 SN - 1431-472X T2 - Informatik ’97 Informatik als Innovationsmotor TI - Parallel Computing in Paderborn: The SFB 376 “Massive Parallelism — Algorithms, Design Methods, Applications” ER - TY - CONF AU - Bock, Stefan AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2175 T2 - IPPS TI - Optimal Wormhole Routing in the (n, d)-Torus ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Oesterdiekhoff, B. AU - Wanka, R. ID - 16699 JF - Algorithmica SN - 0178-4617 TI - Strongly adaptive token distribution ER - TY - BOOK ED - Meyer auf der Heide, Friedhelm ED - Monien, Burkhard ID - 16702 SN - 0302-9743 TI - Automata, Languages and Programming, 23rd International Colloquium, ICALP96 ER - TY - CONF AB - We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality. AU - Grigoriev, Dima AU - Karpinski, Marek AU - Meyer auf der Heide, Friedhelm AU - Smolensky, Roman ID - 17419 T2 - Proc. of 28th ACM-STOC TI - A lower bound for randomized algebraic decision trees VL - 65453 ER - TY - CONF AB - In this paper we develop a model for communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. The implementation of the service network is done on a free configurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi-linear function. The cost model includes the parameters packet size, send hot spot, and the number of processors accessing global variables. These parameters influence the communication time in a high degree and capture important parameters like contention. We implement a Bitonic Sort and a Connected Components algorithm (among others) and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programmer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on-line the optimal parameter values for an access to a global variable achieves good speed ups. AU - Fischer, Matthias AU - Rethmann, Jochen AU - Wachsmann, Alf ID - 17483 SN - 905199267X T2 - 3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96) TI - A Realistic Cost Model for the Communication Time in Parallel Programs ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2183 T2 - FOCS TI - Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols ER - TY - JOUR AU - Schwarze, Frank AU - Meyer auf der Heide, Friedhelm AU - Schröder, Klaus ID - 19958 JF - Euro-Par 1996 TI - Routing on Networks of Optical Crossbars (Extended Abstract). VL - I ER - TY - CHAP AU - Berenbrink, Petra AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 16703 SN - 0302-9743 T2 - STACS 96 TI - Fault-tolerant shared memory simulations ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2184 T2 - SOFSEM TI - Communication in Parallel Systems VL - 1175 ER - TY - JOUR AU - Karp, R. M. AU - Luby, M. AU - Meyer auf der Heide, Friedhelm ID - 16700 JF - Algorithmica SN - 0178-4617 TI - Efficient PRAM simulation on a distributed memory machine ER - TY - GEN AB - In this report, we develop a cost model for the communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. Because we do not have a parallel computer at our disposal that is equipped with a service network, we emulate the service network on a reconfigurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multilinear function. The cost model includes the parameters packet size, send hot spot (the number of messages sent out by one processor), and number of processors accessing global variables. We show that these parameters influence the communication time in a high degree and capture important parameters like network contention. We implement a Bitonic Sort, Sample Sort, Matrix Multiplication, and Connected Components algorithm, and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. We explore the interaction of hot spots and asynchrony and show that the influence of hot spots to the communication time is not as high as one would expect from theoretical considerations in a synchronous model. Therefore, we do not apprehend the hot spot in our cost model. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines online the optimal parameter values for an access to a global variable achieves good speed ups. AU - Fischer, Matthias AU - Rethmann, Jochen AU - Wachsmann, Alf ID - 18352 TI - A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware ER - TY - CONF AU - Cypher, Robert AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian AU - Vöcking, Berthold ID - 2186 T2 - STOC TI - Universal Algorithms for Store-and-Forward and Wormhole Routing ER - TY - THES AU - Scheideler, Christian ID - 2181 TI - Universal routing strategies ER - TY - JOUR AU - Ameur, Foued AU - Fischer, Paul AU - Höffgen, Klaus -U. AU - Meyer auf der Heide, Friedhelm ID - 16698 JF - Acta Informatica SN - 0001-5903 TI - Trial and error. A new approach to space-bounded learning ER - TY - JOUR AU - Gil, Joseph AU - Meyer auf der Heide, Friedhelm AU - Wigderson, Avi ID - 16701 JF - SIAM Journal on Computing SN - 0097-5397 TI - The Tree Model for Hashing: Lower and Upper Bounds ER - TY - GEN AU - Czumaj, Artur AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 17418 TI - Contention Resolution in Hashing Based Shared Memory Simulations ER - TY - CHAP AU - Bäumker, Armin AU - Dittrich, Wolfgang AU - Meyer auf der Heide, Friedhelm AU - Rieping, Ingo ID - 17564 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Realistic parallel algorithms: Priority queue operations and selection for the BSP* Model ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian AU - Stemann, Volker ID - 2182 IS - 2 JF - Theor. Comput. Sci. TI - Exploiting Storage Redundancy to Speed up Randomized Shared Memory Simulations ER - TY - CONF AU - Czumaj, A. AU - Meyer auf der Heide, Friedhelm AU - Stemann, V. ID - 16707 SN - 0818669152 T2 - Proceedings Third Israel Symposium on the Theory of Computing and Systems TI - Improved optimal shared memory simulations, and the power of reconfiguration ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian AU - Stemann, Volker ID - 2208 T2 - STACS TI - Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Vöcking, Berthold ID - 16704 SN - 0302-9743 T2 - STACS 95 TI - A packet routing protocol for arbitrary networks ER - TY - CHAP AU - Bäumker, Armin AU - Dittrich, Wolfgang AU - Meyer auf der Heide, Friedhelm ID - 16874 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Truly efficient parallel algorithms: c-optimal multisearch for an extension of the BSP model ER - TY - CHAP AU - Czumaj, Artur AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 16705 SN - 0302-9743 T2 - Lecture Notes in Computer Science TI - Shared memory simulations with triple-logarithmic delay ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Westermann, Matthias ID - 16717 SN - 0302-9743 T2 - Graph-Theoretic Concepts in Computer Science TI - Hot-potato routing on multi-dimensional tori ER - TY - THES AU - Czumaj, Artur ID - 19627 SN - 3-931466-07-8 TI - Parallel Algorithmic Techniques: PRAM Algorithms and PRAM Simulations ER - TY - THES AU - Ameur, Foued ID - 19634 SN - 3-931466-09-4 TI - Space-Bounded Learning Algorithms ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Storch, Martin AU - Wanka, Rolf ID - 16706 SN - 0897917170 T2 - Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures - SPAA '95 TI - Optimal trade-offs between size and slowdown for universal parallel networks ER - TY - CONF AU - Czumaj, Artur AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 17482 T2 - Proceedings of the 2nd IEEE Workshop on Reconfigurable Architectures TI - Simulating shared memory in real time: On the computation power of reconfigurable meshes ER - TY - JOUR AU - Breslauer, Dany AU - Czumaj, Artur AU - Dubhashi, Devdatt P. AU - Meyer auf der Heide, Friedhelm ID - 16566 JF - Information Processing Letters SN - 0020-0190 TI - Transforming comparison model lower bounds to the parallel-random-access-machine ER - TY - THES AU - Wachsmann, Alf ID - 19630 SN - 3-931466-05-1 TI - Eine Bibliothek von Basisdiensten für Parallelrechner: Routing, Synchronisation, gemeinsamer Speicher ER - TY - THES AU - Stemann, Volker ID - 19623 SN - 3-931466-02-7 TI - Contention Resolution in Hashing Based Shared Memory Simulations ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2187 T2 - ESA TI - Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 2207 T2 - SPAA TI - Space-Efficient Routing in Vertex-Symmetric Networks (Extended Abstract) ER - TY - THES AU - Wanka, Rolf ID - 19624 TI - Paralleles Sortieren auf mehrdimensionalen Gittern ER - TY - JOUR AU - Dietzfelbinger, Martin AU - Karlin, Anna AU - Mehlhorn, Kurt AU - Meyer auf der Heide, Friedhelm AU - Rohnert, Hans AU - Tarjan, Robert E. ID - 16728 JF - SIAM Journal on Computing SN - 0097-5397 TI - Dynamic Perfect Hashing: Upper and Lower Bounds ER - TY - BOOK ED - Meyer auf der Heide, Friedhelm ED - Monien, B. ED - Rosenberg, A. L. ID - 17477 SN - 0302-9743 TI - Parallel Architectures and Their Efficient Use ER - TY - CHAP AU - Meyer auf der Heide, Friedhelm AU - Oesterdiekhoff, Brigitte AU - Wanka, Rolf ID - 16730 SN - 0302-9743 T2 - Automata, Languages and Programming TI - Strongly adaptive token distribution ER - TY - CONF AU - Dietzfelbinger, Martin AU - Meyer auf der Heide, Friedhelm ID - 16731 SN - 0897915992 T2 - Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures - SPAA '93 TI - Simple, efficient shared memory simulations ER - TY - JOUR AU - Dietzfelbinger, M. AU - Meyer auf der Heide, Friedhelm ID - 16729 JF - Information and Computation SN - 0890-5401 TI - An Optimal Parallel Dictionary ER - TY - CONF AU - Kastens, Uwe AU - Meyer auf der Heide, Friedhelm AU - Wachsmann, Alf AU - Wichmann, Friedrich ID - 17479 T2 - Proc. 3rd PASA Workshop, PARS Mitteilungen TI - OCCAM-light: A Language Combining Shared Memory and Message Passing (A First Report) ER - 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 - 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 - JOUR AB -