@article{16504,
  author       = {{Bäumker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm}},
  issn         = {{0304-3975}},
  journal      = {{Theoretical Computer Science}},
  pages        = {{175--203}},
  title        = {{{Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model}}},
  doi          = {{10.1016/s0304-3975(98)00020-6}},
  year         = {{1998}},
}

@inbook{16562,
  author       = {{Meyer auf der Heide, Friedhelm and Martinez, Gabriel Terán}},
  booktitle    = {{LATIN'98: Theoretical Informatics}},
  isbn         = {{9783540642756}},
  issn         = {{0302-9743}},
  title        = {{{Communication-efficient parallel multiway and approximate minimum cut computation}}},
  doi          = {{10.1007/bfb0054332}},
  year         = {{1998}},
}

@inproceedings{16563,
  author       = {{Cole, Richard and Maggs, Bruce M. and Meyer auf der Heide, Friedhelm and Mitzenmacher, Michael and Richa, Andréa W. and Schröder, Klaus and Sitaraman, Ramesh K. and Vöcking, Berthold}},
  booktitle    = {{Proceedings of the thirtieth annual ACM symposium on Theory of computing  - STOC '98}},
  isbn         = {{0897919629}},
  title        = {{{Randomized protocols for low-congestion circuit routing in multistage interconnection networks}}},
  doi          = {{10.1145/276698.276790}},
  year         = {{1998}},
}

@phdthesis{19631,
  author       = {{Bäumker, Armin}},
  isbn         = {{3-931466-27-2}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Communication Efficient Parallel Searching}}},
  volume       = {{28}},
  year         = {{1997}},
}

@phdthesis{19636,
  author       = {{Dittrich, Wolfgang}},
  isbn         = {{3-931466-26-4}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Communication and I/O Efficient Parallel Data Structures}}},
  volume       = {{27}},
  year         = {{1997}},
}

@phdthesis{19637,
  author       = {{Strothmann, Willy-Bernhard}},
  isbn         = {{3-931466-34-5}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Bounded Degree Spanning Trees}}},
  volume       = {{35}},
  year         = {{1997}},
}

@inproceedings{19869,
  abstract     = {{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$.}},
  author       = {{Czumaj, Artur and Strothmann, Willy-Bernhard}},
  booktitle    = {{Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)}},
  isbn         = {{9783540633976}},
  issn         = {{0302-9743}},
  title        = {{{Bounded degree spanning trees}}},
  doi          = {{10.1007/3-540-63397-9_9}},
  year         = {{1997}},
}

@techreport{18955,
  abstract     = {{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.}},
  author       = {{Strothmann, Willy-Bernhard and Lukovszki, Tamás}},
  title        = {{{Decremental Biconnectivity on Planar Graphs}}},
  year         = {{1997}},
}

@inproceedings{18575,
  author       = {{Sohler, Christian and Denny, Markus}},
  booktitle    = {{Proceedings of the 9th Canadian Conference on Computational Geometry}},
  pages        = {{39--43}},
  title        = {{{Encoding a Triangulation as a Permutation of its Point Set}}},
  year         = {{1997}},
}

@inproceedings{2175,
  author       = {{Bock, Stefan and Meyer auf der Heide, Friedhelm and Scheideler, Christian}},
  booktitle    = {{IPPS}},
  pages        = {{326----332}},
  publisher    = {{IEEE Computer Society}},
  title        = {{{Optimal Wormhole Routing in the (n, d)-Torus}}},
  year         = {{1997}},
}

@inproceedings{2179,
  author       = {{Flammini, Michele and Scheideler, Christian}},
  booktitle    = {{SPAA}},
  pages        = {{170----179}},
  title        = {{{Simple, Efficient Routing Schemes for All-Optical Networks}}},
  year         = {{1997}},
}

@article{16564,
  author       = {{Grigoriev, Dima and Karpinski, Marek and Meyer auf der Heide, Friedhelm and Smolensky, Roman}},
  issn         = {{1016-3328}},
  journal      = {{computational complexity}},
  pages        = {{357--375}},
  title        = {{{A lower bound for randomized algebraic decision trees}}},
  doi          = {{10.1007/bf01270387}},
  year         = {{1997}},
}

@article{16565,
  author       = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}},
  issn         = {{0890-5401}},
  journal      = {{Information and Computation}},
  pages        = {{103--120}},
  title        = {{{Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures}}},
  doi          = {{10.1006/inco.1997.2642}},
  year         = {{1997}},
}

@article{16567,
  author       = {{Meyer auf der Heide, Friedhelm and Storch, M. and Wanka, Rolf}},
  issn         = {{1432-4350}},
  journal      = {{Theory of Computing Systems}},
  pages        = {{627--644}},
  title        = {{{Optimal Tradeoffs Between Size and Slowdown for Universal Parallel Networks}}},
  doi          = {{10.1007/s002240000071}},
  year         = {{1997}},
}

@inbook{16569,
  author       = {{Meyer auf der Heide, Friedhelm and Vöcking, Berthold}},
  booktitle    = {{Euro-Par'97 Parallel Processing}},
  isbn         = {{9783540634409}},
  issn         = {{0302-9743}},
  title        = {{{Static and dynamic data management in networks}}},
  doi          = {{10.1007/bfb0002716}},
  year         = {{1997}},
}

@inproceedings{16604,
  author       = {{Berenbrink, Petra and Meyer auf der Heide, Friedhelm and Schröder, Klaus}},
  booktitle    = {{Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures  - SPAA '97}},
  isbn         = {{0897918908}},
  title        = {{{Allocating weighted jobs in parallel}}},
  doi          = {{10.1145/258492.258522}},
  year         = {{1997}},
}

@inbook{16605,
  author       = {{Bäumker, Armin and Meyer auf der Heide, Friedhelm}},
  booktitle    = {{Solving Irregularly Structured Problems in Parallel}},
  isbn         = {{9783540631385}},
  issn         = {{0302-9743}},
  title        = {{{Communication efficient parallel searching}}},
  doi          = {{10.1007/3-540-63138-0_21}},
  year         = {{1997}},
}

@inbook{16687,
  author       = {{Karaivazoglou, Efstratios and Meyer auf der Heide, Friedhelm}},
  booktitle    = {{Euro-Par'97 Parallel Processing}},
  isbn         = {{9783540634409}},
  issn         = {{0302-9743}},
  title        = {{{Routing on asyncronous processor networks}}},
  doi          = {{10.1007/bfb0002741}},
  year         = {{1997}},
}

@inproceedings{16689,
  author       = {{Maggs, B.M. and Meyer auf der Heide, Friedhelm and Vöcking, Berthold and Westermann, Matthias}},
  booktitle    = {{Proceedings 38th Annual Symposium on Foundations of Computer Science}},
  isbn         = {{0818681977}},
  title        = {{{Exploiting locality for data management in systems of limited bandwidth}}},
  doi          = {{10.1109/sfcs.1997.646117}},
  year         = {{1997}},
}

@inbook{16693,
  author       = {{Meyer auf der Heide, Friedhelm and Decker, Thomas}},
  booktitle    = {{Informatik ’97 Informatik als Innovationsmotor}},
  isbn         = {{9783540630661}},
  issn         = {{1431-472X}},
  title        = {{{Parallel Computing in Paderborn: The SFB 376 “Massive Parallelism — Algorithms, Design Methods, Applications”}}},
  doi          = {{10.1007/978-3-642-60831-5_22}},
  year         = {{1997}},
}