UIB-1995-01 On the Largest Common Subgraph Problem

Autoren: Oleg Verbitsky

Given two graphs G_1=langle V_1,E_1rangle and G_2=langle V_2,E_2rangle, |V_1|=|V_2|=n, to determine whether they have a size-k common subgraph is one of the earliest examples of an NP-complete problem (by a trivial reduction from the Maximum Clique problem). We show that this problem for equally sized G_1 and G_2, i.e. when |E_1|=|E_2|=m, remains NP-complete. Moreover, the restriction to the case k=m-sqrt[c]n, c>1, is also NP-complete. In this result k and m can hardly be made tighter because the largest Common Subgraph problem for equally sized graphs is reducible to the Graph Isomorphism problem in time n^{O(m-k). Further, we consider the optimization problem of computing the maximum common subgraph size. It is only known that this problem is not harder than computing the maximum clique size (V.Kann, STACS'92), and that it approximable within factor O(frac nn) (M.Hall\-d\'orsson, 1994). For some epsilonin(0,1), we prove that the largest common subgraph size is not approximable within addend n^epsilon unless NP=PP. The techniques used are reductions from the problem of distinguishing between graphs with large and small clique size.

PDF

UIB-1995-02 Complexity of Presburger Arithmetic with Fixed Quantifier Dimension

Autoren: Uwe Schöning

It is shown that the decision problem for formulas in Presburger arithmetic with quantifier prefix [exists_1forall_2dots exists_mforall^3] (for m odd) and [exists_1forall_2dots forall_mexists^3] (for m even) is complete for the class Sigma_m^P of the polynomial-time hierarchy. Furthermore, the prefix type [existsforallexistsexists] is complete for Sigma_2^P, and the prefix type [existsforall] is complete for NP. This improves results (and solves a problem left open) by Gr\ädel.

PDF

UIB-1995-03 The Complexity of Generating and Checking Proofs of Membership

Autoren: Harry Buhrman,Thomas Thierauf

PDF

UIB-1995-04 Structural Average Case Complexity

Autoren: Rainer Schuler, Tomoyuki Yamakami

Levin introduced an average-case complexity measure, based on a notion of ''polynomial on mu-average,'' and defined ''average-case polynomial-time many-one reducibility'' among randomized decision problems. We generalize his notions of average-case complexity classes, Random-NP and {Average-P

PDF

UIB-1995-05 Architecture Indepentent Massive Parallelization of Divide-And-Conquer Algorithms

Autoren: Klaus Achatz, Wolfram Schulte

We present a stategy to develop, in a functional setting, correct, efficient and portable Divide-and-Conquer (DC) programs for massively parallel architectures. Starting from an operational DC program, mapping sequences to sequences, we apply a set of semantics preserving transformation rules, which transform the parallel control stucture of DC into a sequential control flow, therby making the implicit data parallelism in a DC scheme explicit. In the next phase of our strategy, the parallel architecture is fully expressed, where ärchitecture dependent" higher-order functions are introduced. Then - due to the rising communication complexities on particular architectures - topology dependent communication patterns are optimized in order to reduce the overall communication coats. The advantages of this approach are manifold and are demonstraded with a set of non-trivial examples.

PDF

UIB-1995-06 Structure in Average Case Complexity

Autoren: Christoph Karg, Rainer Schuler

In many practical applications the average case behavior of an algorithm is of more interest than its worst case complexity. A decade ago Levin gave a general framework for average case analysis and opened on this way a new field of research, a theory of average case complexity. In this paper we use a characterization from Schapire which gives a very smooth translation from worst case complexity to average case complexity of the notions for time and space complexity. We prove tight space- and time-hierarchy theorems and discuss the structure of deterministic and nondeterministic average-case complexity classes. In particular, we show for polynomial and exponential time- and space-bounded classes that nondeterministic average case is equivalent to deterministic average case if and only if this is true in worst case complexity. We consider tally codings of randomized decision problems and show that there are tally randomized decision problems in average nondeterministic exponential time which are not in average deterministic exponential time if and only if average deterministic polynomial time is different from average nondeterministic polynomial time.

PDF

UIB-1995-07 ADEPT: Ein integrierender Ansatz zur Entwicklung flexibler, zuverlässiger kooperierender Assistenzsysteme in klinischen Anwendungsumgebungen

Autoren: P. Dadam, K. Kuhn, M. Reichert, T. Beuter, M. Nathe

Die Entwicklung flexibler, kooperierender Assistenzsysteme mit der für den klinischen Bereich unerlässlichen Zuverlässigkeit ist auf Basis der heutigen Softwaretechnologie immer noch ein äu§erst schwieriges und aufwendiges Unterfangen. In diesem Beitrag wird ein neuer Ansatz vorgestellt, der durch strikte Trennung und Kapselung von Ablauflogik sowie Ausnahme- und Fehlerbehandlung vom eigentlichen Anwendungsprogramm die Komplexität für den Anwendungsentwickler erheblich zu reduzieren vermag.

PDF

UIB-1995-08 Aufbereitung von gescannten Röntgenbildern zur filmlosen Diagnostik

Autoren: Jürgen Kehrer, Peter Schulthess

Ziel dieses Projektes ist die Übertragung von Röntgenbildern von einer zentralen Stelle, an der die Bilder digitalisiert und gespeichert werden, zu entfernten Empfangsstationen. Um die Transferdauer zu verkürzen und für die Archivierung auf CD-R werden die Bilder komprimiert. Als Übertragungsmedium zwischen den Kliniken kommt sowohl ISDN als auch ETHERNET in Frage. Die (erste) Befundung der Röntgenbilder soll am Bildschirm stattfinden. Die Orginale der Röntgenfilme werden in den meisten Fällen zur Diagnosestellung nicht mehr benötigt. Soweit die Theorie. Leider treten bei der Digitalisierung und Komprimierung Qualitätseinbußen auf. Diese lassen sich aber durch geeignete Scanner-Hardware, Justierung und Algorithmen klein halten. Ein größeres Problem stellt das Ausgabemedium Bildschirm dar. Ein Standardbildschirm kann nur 256 verschiedenen Graustufen anzeigen. Ein Röntgenfilm besitzt aber einen Grauwertumfang von mehr als 700 Graustufen. Das Problem besteht nun darin, diese 700 Graustufen auf die 256 Graustufen des Bildschirms abzubilden. Die einfachste Möglichkeit ist die interaktive Einstellung von Helligkeit und Kontrast (window and center control) für das gesamte Bild oder auch nur für einen Bildausschnitt. Die Histogrammequalisierung (HE) liefert diese Einstellung für Bilder mit eingeschränktem Grauwertbereich automatisch. Die besten Ergebnisse erzielt man mit der adaptiven Histogramm-Equalisierung (AHE) zur Reduktion der 700 Grauwerte. Durch Segmentierung des Bildes in viele kleine Bereiche, für die jeweils eine eigene Transferfunktion berechnet wird, erreicht man eine globale Reduzierung der Grauwerte ohne große Verluste an Grauwertauflösung in den einzelnen Bereichen.

PDF

UIB-1995-09 On Sets Turing Reducible to P-Selective Sets

Autoren: Hans-Jörg Burtschick, Wolfgang Lindner

We consider sets Turing reducible to p-selective sets under various resource bounds and restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP/poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP can not reduced to the p-selective sets under 2^{lin time reductions with at most n^k queries for any emph{fixed

PDF

UIB-1995-10 Berücksichtigung lokaler Randbedingung bei globaler Zieloptimierung mit neuronalen Netzen am Beispiel Truck Backer-Upper

Autoren: Boris Hartmann

PDF

UIB-1995-11 Prinzipien der Replikationskontrolle in verteilten Systemen

Autoren: Thomas Beuter, Peter Dadam

Durch Datenreplikation können prinzipiell schnellere Zugriffszeiten und eine beliebig hohe Fehlertoleranz in einem verteilten System erreicht werden. Ein repliziertes verteiltes System muß allerdings zur Konsistenzsicherung zusätzliche Aufgaben erfüllen. Dazu wurden in der Literatur viele unterschiedliche Replikationsverfahren vorgeschlagen. Dieser Artikel beschreibt die zusätzlichen Aufgaben kurz, leitet daraus Kriterien zur Klassifikation der verschiedenen Prinzipien der Replikationskontrolle ab und stellt danach einige der Replikationsverfahren detaillierter vor.

PDF

UIB-1995-12 Massive Parallelization of Divide-and-Conquer Algorithms over Powerlists

Autoren: Klaus Achatz, Wolfram Schulte

We present transformation rules to parallelize Divide-and-Conquer (DC) algorithms over powerlists. These rules convert the parallel control stucture of DC into a sequential control flow, thereby making the implicit massive data parallelism in a DC scheme explicit. The results given here are illustrated by many examples including Fast Fourier Transform and Batcher`s bitonic sort.

PDF

UIB-1995-13 Efficient Call-by-value Evaluation Strategy of Primitive Recursive Program Schemes

Autoren: Andrea Mößle, Heiko Vogler

We present transformation rules to parallelize Divide-and-Conquer (DC) algorithms over powerlists. These rules convert the parallel control structure of DC into a sequential control flow, thereby making the implicit massive data parallelism in a DC scheme explicit. The results given here are illustrated by many examples including Fast Fourier Transform and Batcher's bitonic sort

PDF

UIB-1995-14 A Generic Specification for Verifying Peephole Optimizations

Autoren: Axel Dold, Friedrich W. von Henke, Holger Pfeifer, Harald Rueß

PDF