For an arbitrary fixed surface S, a linear time algorithm is presented that for a given graph G
either finds an embedding of G in S or identifies a subgraph of G that is homeomorphic to a …

Abstract The Rotating Calipers is a paradigm used to solve a number of problems in the field
of Computational Geometry. The original algorithm was presented by Shamos in 1978 in …

Lower bounds are developed for the processor—time tradeoffs of machines such as linear
arrays and two-dimensional meshes, which are compatible with the physical limitation on …

Probabilistic techniques are becoming more and more important in Computer Science.
Some of them are useful for the analysis of algorithms. The aim of this thesis is to describe …

We extend Levin's definition of average polynomial time to arbitrary time-bounds in
accordance with the following general principles:(1) It essentially agrees with Levin's notion …

Abstract we consider the problem of constructing a static dictionary that supports access
queries for a set of w-bit keys on a wbit RAM with an arithmetic instruction set consisting of …

As software systems grow in size and sophistication, it becomes harder for humans to
understand them and anticipate their behavior. Formal specification techniques aim to foster …

Probabilistic techniques are becoming more and more important in Computer Science.
Some of them are useful for the analysis of algorithms. The aim of this thesis is to describe …

Die vorliegende Arbeit beschäftigt sich mit der Entwicklung und Optimierung verteilter
Algorithmen zu Problemen aus der Zahlentheorie. Speziell werden vier Probleme …

Wie wir eingangs bereits gesehen haben, ist das TM-Modell ausreichend, um Fragen der
Berechenbarkeit zu untersuchen. Eine TM hat jedoch mit einem modernen Computer wenig …