h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Searching for many defective edges in hypergraphs = Suchen nach vielen defekten Kanten in Hypergraphen



Verantwortlichkeitsangabevorgelegt von Jessica Emonts, geb. Troes

ImpressumAachen : Publikationsserver der RWTH Aachen University 2013

UmfangVIII, 104 S., graph. Darst.


Aachen, Techn. Hochsch., Diss., 2013


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2013-07-05

Online
URN: urn:nbn:de:hbz:82-opus-47403
URL: https://publications.rwth-aachen.de/record/229036/files/4740.pdf

Einrichtungen

  1. Fachgruppe Mathematik (110000)
  2. Lehrstuhl II für Mathematik (für Ingenieure) (113210)

Inhaltliche Beschreibung (Schlagwörter)
Gruppentest (Genormte SW) ; Hypergraph (Genormte SW) ; Mathematik (frei) ; group testing (frei) ; hypergraph (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Angenommen wir haben einen Hypergraphen H=(V,E) gegeben. Einige der Kanten in H besitzen eine ausgezeichnete Eigenschaft. Diese nennen wir defekte Kanten und ihre Menge wollen wir mit D bezeichnen. Um die defekten Kanten zu finden, stehen uns sogenannte Gruppentests zur Verfügung. Ein Gruppentest gibt uns für jede beliebige Eckmenge an, ob mindestens eine der defekten Kanten vollständig in der Menge liegt oder nicht. In der vorliegenden Arbeit untersuchen wir die Zahl der Tests, die ein sequentieller Algorithmus (alle Tests werden nacheinander und in Abhängigkeit der vorherigen Antworten bestimmt) im Worst Case benötigt, um alle defekten Kanten zu finden. Ist zu Beginn der Suche bekannt, dass genau d Kanten defekt sind, so gibt es |E|! / (d!•(|E|-d)!) Möglichkeiten D auszuwählen. Pro Test werden im Worst Case nicht mehr als die Hälfte der Möglichkeiten ausgeschlossen, also benötigt jeder Suchalgorithmus im Worst Case mindestens log2(|E|! / (d!•(|E|-d)!)) Tests, um alle defekten Kanten zu finden. Diese untere Schranke heißt die Informationstheoretische Schranke und ist die beste bekannte untere Schranke für das Gruppentestproblem auf Hypergraphen. Die beste bekannte obere Schranke wurde von Chen und Hwang 2007 bewiesen, sie zeigten, dass es einen Suchalgorithmus gibt, der im Worst Case nicht mehr als d • ceil(log2(|E|))+(r-1)^ceil( r/2 )• d^r+o(d^r) Tests benötigt, um alle defekten Kanten in einem Hypergraphen vom Rang <= r zu finden. Zunächst geben wir eine schärfere untere Schranke an, dazu konstruieren wir einen Hypergraphen vom Rang r mit defekter Kantenmenge D, |D|=d, sodass die defekten Kanten im Worst Case nicht mit weniger als d • log2(|E|) + (1/r)^r/2 • d^r/2 Tests gefunden werden können. Anschließend stellen wir einen Suchalgorithmus vor, der alle defekten Kanten in einem Hypergraphen vom Rang 3 mit höchstens d •ceil(log2|E|)+ 2sqrt(d) + 10d + 24d^3/2 Tests findet. Danach präsentieren wir einen Algorithmus für allgemeine Hypergraphen vom Rang r, der alle d defekte Kanten mit maximal d •ceil(log2|E|)+ O(d^r/2) Tests findet. Der letzte Teil der Arbeit beschäftigt sich mit dem Spezialfall von 3-uniformen Hypergraphen. Wir stellen einen Algorithmus vor, der alle defekten Kanten mit höchstens d •ceil(log2 (|E|/d))+ O(d)Tests findet. Damit beweisen wir für 3-uniforme Hypergraphen eine Vermutung von Du und Hwang.

Suppose we are given a hypergraph H = (V,E). Some of the edges in H have a distinguished property, we call these edges defective edges and denote their set by D. To find the defective edges, we use so called group tests. A group test tells us for any vertex set whether at least one defective edge lies completely in the vertex set or not. In the present work we investigate the number of tests that a sequential algorithm (all tests are stated one after the other and in dependence of the previous answers) needs in the worst case to find all defective edges. Is at the beginning of the search known that exactly d edges are defective, then there are |E|! / (d!•(|E|-d)!)) possibilities to choose D. In the worst case, per test not more than half the possibilities are excluded, thus any search algorithm needs in the worst case at least log2(|E|! / (d!•(|E|-d)!)) tests to find all defective edges. This lower bound is the information theoretic bound and is the best known lower bound for the group testing problem on hypergraphs. The best known upper bound was proven by Chen and Hwang in 2007. They showed that there is a search algorithm that needs in the worst case not more than d • ceil(log2(|E|))+(r-1)^ceil( r/2 ) • d^r+o(d^r) tests to find all defective edges in a hypergraph of rank <=r. At first we state a sharper lower bound, therefore we construct a hypergraph of rank r with defective edge set D, |D| = d, so that in the worst case the defective edges cannot be found with less than d • log2(|E|) + (1/r)^r/2 • d^r/2 tests. Thereafter we present a search algorithm, that finds all defective edges in a hypergraph of rank 3 with at most d •ceil(log2|E|)+ 2sqrt(d) + 10d + 24d^3/2 tests. Then we give an algorithm for general hypergraphs of rank r, that finds all defective edges by at most d •ceil(log2|E|)+ O(d^r/2) tests. In the last part of the thesis we consider the special case of 3-uniform hypergraphs. We introduce an algorithm that finds all defective edges with at most d •ceil(log2 (|E|/d))+ O(d) tests. Which proves for 3-uniform hypergraphs a conjecture of Du and Hwang.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Interne Identnummern
RWTH-CONV-144013
Datensatz-ID: 229036

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Faculty of Mathematics, Computer Science and Natural Sciences (Fac.1) > Department of Mathematics
Publication server / Open Access
Public records
Publications database
113210
110000

 Record created 2014-07-16, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)