@inproceedings{18959,
  abstract     = {{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.<br><br>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.<br><br>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.}},
  author       = {{Lukovszki, Tamás}},
  booktitle    = {{Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99), LNCS}},
  isbn         = {{9783540662792}},
  issn         = {{0302-9743}},
  pages        = {{193--204}},
  title        = {{{New Results on Fault Tolerant Geometric Spanners}}},
  doi          = {{10.1007/3-540-48447-7_20}},
  year         = {{1999}},
}

@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}},
}

@inproceedings{18576,
  abstract     = {{In this paper we deal with two problems on star-shaped polygons. First, we present a Las-Vegas algorithm that uniformly at random creates a star-shaped polygon whose vertices are given by a point set ( S ) of ( n ) points in the plane that does not admit degenerate star-shaped polygons. The expected running time of the algorithm is ( O(n^2log n) ) and it uses ( O(n) ) memory. We call a star-shaped polygon degenerate if its kernel has 0 area.<br><br>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.}},
  author       = {{Sohler, Christian}},
  booktitle    = {{Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99)}},
  pages        = {{174--177}},
  title        = {{{Generating Random Star-Shaped Polygons}}},
  year         = {{1999}},
}

@inproceedings{2210,
  author       = {{Berenbrink, Petra and Riedel, Marco and Scheideler, Christian}},
  booktitle    = {{International Workshop on Communication and Data Management in Large Networks (CDMLarge)}},
  pages        = {{2--12}},
  title        = {{{Design of the PRESTO Multimedia Storage Network (Extended Abstract)}}},
  year         = {{1999}},
}

@inproceedings{2166,
  author       = {{Scheideler, Christian and Vöcking, Berthold}},
  booktitle    = {{STOC}},
  pages        = {{215----224}},
  title        = {{{From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols}}},
  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}},
}

@inbook{17052,
  author       = {{Mayr, E. W. and Meyer auf der Heide, Friedhelm and Wanka, Rolf}},
  booktitle    = {{Informatik aktuell}},
  isbn         = {{9783540664505}},
  issn         = {{1431-472X}},
  title        = {{{International Workshop on Communication and Data Management in Large Networks}}},
  doi          = {{10.1007/978-3-662-01069-3_47}},
  year         = {{1999}},
}

@inbook{17053,
  author       = {{Meyer auf der Heide, Friedhelm and Vöcking, Berthold and Westermann, Matthias}},
  booktitle    = {{Algorithms - ESA’ 99}},
  isbn         = {{9783540662518}},
  issn         = {{0302-9743}},
  title        = {{{Provably Good and Practical Strategies for Non-uniform Data Management in Networks}}},
  doi          = {{10.1007/3-540-48481-7_9}},
  year         = {{1999}},
}

@phdthesis{19639,
  author       = {{Vöcking, Berthold}},
  isbn         = {{3-931466-45-0}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Static and Dynamic Data Management in Networks}}},
  volume       = {{46}},
  year         = {{1998}},
}

@techreport{19735,
  abstract     = {{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.}},
  author       = {{Bonorden, Olaf and Rieping, Ingo and von Otte, Ingo and Juurlink, Bernhardus}},
  title        = {{{The Paderborn University BSP (PUB) Library - Design, Implementation and Performance}}},
  year         = {{1998}},
}

@inbook{17412,
  abstract     = {{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.
}},
  author       = {{Fischer, Matthias and Lukovszki, Tamás and Ziegler, Martin}},
  booktitle    = {{Algorithms — ESA’ 98}},
  isbn         = {{9783540648482}},
  issn         = {{0302-9743}},
  title        = {{{Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time}}},
  doi          = {{10.1007/3-540-68530-8_14}},
  year         = {{1998}},
}

@inproceedings{17863,
  abstract     = {{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.
}},
  author       = {{Fischer, Matthias and Lukovszki, Tamas and Ziegler, Martin }},
  booktitle    = {{Algorithm Engineering, 2nd International Workshop, {WAE '98}}},
  pages        = {{133----142}},
  publisher    = {{Max-Planck-Institut für Informatik}},
  title        = {{{A Network Based Approach for Realtime Walkthrough of Massive Models}}},
  year         = {{1998}},
}

@techreport{18145,
  abstract     = {{Preis für den Beitrag "Multimediale Entdeckungsreisen unserer Welt mit dem Internet"}},
  author       = {{Ziegler, Martin and Fischer, Matthias and Lukovszki, Tamás}},
  title        = {{{Multimediale Entdeckungsreisen unserer Welt mit dem Internet}}},
  year         = {{1998}},
}

@phdthesis{18445,
  author       = {{Oesterdiekhoff, Brigitte}},
  title        = {{{On Periodic Comparator Networks}}},
  year         = {{1998}},
}

@article{2168,
  author       = {{Scheideler, Christian and Vöcking, Berthold}},
  journal      = {{Theory Comput. Syst.}},
  number       = {{4}},
  pages        = {{425----449}},
  title        = {{{Universal Continuous Routing Strategies}}},
  doi          = {{10.1007/s002240000096}},
  volume       = {{31}},
  year         = {{1998}},
}

@inproceedings{2169,
  author       = {{Adler, Micah and Scheideler, Christian}},
  booktitle    = {{SPAA}},
  pages        = {{259----268}},
  title        = {{{Efficient Communication Strategies for Ad-Hoc Wireless Networks (Extended Abstract)}}},
  year         = {{1998}},
}

@inproceedings{2170,
  author       = {{Feige, Uriel and Scheideler, Christian}},
  booktitle    = {{STOC}},
  pages        = {{624----633}},
  title        = {{{Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract)}}},
  year         = {{1998}},
}

@book{2185,
  author       = {{Scheideler, Christian}},
  isbn         = {{978-3-540-69792-3}},
  title        = {{{Universal Routing Strategies for Interconnection Networks}}},
  doi          = {{10.1007/BFb0052928}},
  volume       = {{1390}},
  year         = {{1998}},
}

@article{16503,
  author       = {{Meyer auf der Heide, Friedhelm and Schröder, Klaus and Schwarze, Frank}},
  issn         = {{0304-3975}},
  journal      = {{Theoretical Computer Science}},
  pages        = {{181--200}},
  title        = {{{Routing on networks of optical crossbars}}},
  doi          = {{10.1016/s0304-3975(97)86791-6}},
  volume       = {{196}},
  year         = {{1998}},
}