@inproceedings{16720, author = {{Bonorden, Olaf and Bruls, N. and Kastens, U. and Le, D. K. and Meyer auf der Heide, Friedhelm and Niemann, J.-C. and Porrmann, M. and Rückert, U. and Slowik, A. and Thies, M.}}, booktitle = {{28th Annual IEEE International Conference on Local Computer Networks}}, title = {{{A holistic methodology for network processor design}}}, doi = {{10.1109/LCN.2003.1243185}}, year = {{2003}}, } @inproceedings{19727, author = {{Bonorden, Olaf and Meyer auf der Heide, Friedhelm and Wanka, Rolf}}, booktitle = {{Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA)}}, pages = {{2202--2208}}, title = {{{Composition of Efficient Nested BSP Algorithms: Minimum Spanning Tree Computation as an Instructive Example}}}, year = {{2002}}, } @article{16489, author = {{Krick, Christof and Meyer auf der Heide, Friedhelm and Räcke, Harald and Vöcking, Bernhard and Westermann, Matthias' }}, issn = {{1432-4350}}, journal = {{Theory of Computing Systems}}, pages = {{217--245}}, title = {{{Data Management in Networks: Experimental Evaluation of a Provably Good Strategy}}}, doi = {{10.1007/s00224-001-1045-z}}, year = {{2002}}, } @inproceedings{16490, abstract = {{We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects. For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk. We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.}}, author = {{Klein, Jan and Krokowski, Jens and Fischer, Matthias and Wand, Michael and Wanka, Rolf and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the ACM symposium on Virtual reality software and technology - VRST '02}}, isbn = {{1581135300}}, title = {{{The randomized sample tree: a data structure for interactive walkthroughs in externally stored virtual environments}}}, doi = {{10.1145/585740.585764}}, year = {{2002}}, } @inproceedings{16491, author = {{Meyer auf der Heide, Friedhelm and Schindelhauer, Christian and Volbert, Klaus and Grünewald, Matthias}}, booktitle = {{Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '02}}, isbn = {{1581135297}}, title = {{{Energy, congestion and dilation in radio networks}}}, doi = {{10.1145/564870.564910}}, year = {{2002}}, } @inbook{16723, author = {{Meyer auf der Heide, Friedhelm and Kumar, Mohan and Nikoletseas, Sotiris and Spirakis, Paul}}, booktitle = {{Euro-Par 2002 Parallel Processing}}, isbn = {{9783540440499}}, issn = {{0302-9743}}, title = {{{Mobile Computing, Mobile Networks}}}, doi = {{10.1007/3-540-45706-2_133}}, year = {{2002}}, } @article{2139, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, journal = {{Combinatorica}}, number = {{1}}, pages = {{95----138}}, title = {{{Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols}}}, doi = {{10.1007/s004930170007}}, volume = {{21}}, year = {{2001}}, } @inproceedings{16492, abstract = {{We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 10^14 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.}}, author = {{Wand, Michael and Fischer, Matthias and Peter, Ingmar and Meyer auf der Heide, Friedhelm and Straßer, Wolfgang}}, booktitle = {{Proceedings of the 28th annual conference on Computer graphics and interactive techniques - SIGGRAPH '01}}, isbn = {{158113374X}}, title = {{{The randomized z-buffer algorithm}}}, doi = {{10.1145/383259.383299}}, year = {{2001}}, } @inbook{16493, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Graph-Theoretic Concepts in Computer Science}}, isbn = {{9783540427070}}, issn = {{0302-9743}}, title = {{{Data Management in Networks}}}, doi = {{10.1007/3-540-45477-2_2}}, volume = {{2204}}, year = {{2001}}, } @inbook{16494, author = {{Meyer auf der Heide, Friedhelm and Wanka, Rolf}}, booktitle = {{Computational Science - ICCS 2001}}, isbn = {{9783540422334}}, issn = {{0302-9743}}, title = {{{Parallel Bridging Models and Their Impact on Algorithm Design}}}, doi = {{10.1007/3-540-45718-6_68}}, year = {{2001}}, } @book{16722, editor = {{Meyer auf der Heide, Friedhelm}}, isbn = {{9783540424932}}, issn = {{0302-9743}}, publisher = {{Springer }}, title = {{{Algorithms — ESA 2001, 9th Annual European Symposium Århus, Denmark}}}, doi = {{10.1007/3-540-44676-1}}, year = {{2001}}, } @techreport{17865, abstract = {{We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of a three dimensional scene of triangular primitives by reconstruction from a random sample of surface points which are chosen with a probability proportional to the projected area of the objects. The approach is independent of mesh connectivity and topology. It leads to a rendering time that grows only logarithmically with the numbers of triangles in the scene and to linear memory consumption, thus allowing walkthroughs of scenes of extreme complexity. We consider different methods for image reconstruction which aim at correctness, rendering speed and image quality and we develop an efficient data structure for sample extraction in output-sensitive time which allows for efficient dynamic updates of the scene. Experiments confirm that scenes consisting of some hundred billion triangles can be rendered within seconds with an image quality comparable to a conventional z-buffer rendering; in special cases, realtime performance can be achieved.}}, author = {{Wand, Michael and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, title = {{{Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes}}}, year = {{2000}}, } @inproceedings{16495, author = {{Meyer auf der Heide, Friedhelm and Räcke, Harald and Westermann, Matthias}}, booktitle = {{Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures - SPAA '00}}, isbn = {{1581131852}}, title = {{{Data management in hierarchical bus networks}}}, doi = {{10.1145/341800.341814}}, year = {{2000}}, } @inproceedings{16496, abstract = {{We present a general framework for the development of on-line algorithms for data management in networks with limited memory capacities. These algorithms dynamically create and delete copies of shared data objects that can be read and written by the nodes in the network. Our algorithms aim to minimize the congestion, i.e., the maximum communication load over all network resources, so that that none of these resources become a communication bottleneck. We give several examples of networks for which our framework yields efficient algorithms, including meshes, fat-trees, hypercubic networks, and complete networks. For example, our framework yields an $O(d cdot log n)$-competitive caching algorithm for $d$-dimensional meshes of size $n$ with respect to the congestion on the communication links, and an $O(1)$-competitive algorithms for complete networks with respect to the congestion at the memory modules due to remote accesses. Previous work on data management in networks either neglects memory capacity constraints or minimizes only the total communication load, i.e., the sum of the communication load over all resources, which may produce congestion as some of the links become bottlenecks.}}, author = {{Meyer auf der Heide, Friedhelm and Vöcking, Berthold and Westermann, Matthias}}, booktitle = {{SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms}}, isbn = {{0898714532}}, pages = {{430–439}}, title = {{{Caching in networks}}}, year = {{2000}}, } @inbook{16497, author = {{Meyer auf der Heide, Friedhelm and Kutyłowski, Mirosław and Ragde, Prabhakar}}, booktitle = {{Euro-Par 2000 Parallel Processing}}, isbn = {{9783540679561}}, issn = {{0302-9743}}, title = {{{Complexity Theory and Algorithms}}}, doi = {{10.1007/3-540-44520-x_59}}, year = {{2000}}, } @article{17010, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{1703--1739}}, title = {{{Contention Resolution in Hashing Based Shared Memory Simulations}}}, doi = {{10.1137/s009753979529564x}}, year = {{2000}}, } @article{16345, author = {{Meyer auf der Heide, Friedhelm and Wanka, Rolf}}, journal = {{ForschungsForum Paderborn}}, pages = {{112--116}}, title = {{{Von der Hollerith-Maschine zum Parallelrechner - Die alltägliche Aufgabe des Sortierens als Fortschrittsmotor für die Informatik}}}, year = {{2000}}, } @inproceedings{18965, author = {{Krick, Christof and Meyer auf der Heide, Friedhelm and Räcke, Harald and Vöcking, Berthold and Westermann, Matthias}}, booktitle = {{Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA '99}}, isbn = {{1581131240}}, pages = {{165--174}}, title = {{{Data management in networks: experimental evaluation of a provably good strategy}}}, doi = {{10.1145/305619.305637}}, year = {{1999}}, } @article{16501, author = {{Meyer auf der Heide, Friedhelm and Vöcking, Berthold}}, issn = {{0196-6774}}, journal = {{Journal of Algorithms}}, pages = {{105--131}}, title = {{{Shortest-Path Routing in Arbitrary Networks}}}, doi = {{10.1006/jagm.1998.0980}}, year = {{1999}}, } @article{16502, author = {{Berenbrink, P. and Meyer auf der Heide, Friedhelm and Schröder, K.}}, issn = {{1432-4350}}, journal = {{Theory of Computing Systems}}, pages = {{281--300}}, title = {{{Allocating Weighted Jobs in Parallel}}}, doi = {{10.1007/s002240000119}}, year = {{1999}}, }