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 - 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 - 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 - Bäumker, Armin ID - 19631 SN - 3-931466-27-2 TI - Communication Efficient Parallel Searching VL - 28 ER - TY - THES AU - Dittrich, Wolfgang ID - 19636 SN - 3-931466-26-4 TI - Communication and I/O Efficient Parallel Data Structures VL - 27 ER - TY - THES AU - Strothmann, Willy-Bernhard ID - 19637 SN - 3-931466-34-5 TI - Bounded Degree Spanning Trees VL - 35 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-Bernhard ID - 19869 SN - 0302-9743 T2 - Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97) TI - Bounded degree spanning trees 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 - 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 - 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 - CONF AU - Flammini, Michele AU - Scheideler, Christian ID - 2179 T2 - SPAA TI - Simple, Efficient Routing Schemes for All-Optical 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 - JOUR AU - Meyer auf der Heide, Friedhelm AU - Storch, M. AU - Wanka, Rolf ID - 16567 JF - Theory of Computing Systems SN - 1432-4350 TI - Optimal Tradeoffs Between Size and Slowdown for Universal Parallel Networks 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, Willy-Bernhard 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 - 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 - 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 - 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 - 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 - CONF AU - Maggs, B.M. AU - Meyer auf der Heide, Friedhelm AU - Vöcking, Berthold AU - Westermann, Matthias 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 -