Searching for many defective edges in hypergraphs

Emonts, Jessica (Author); Triesch, Eberhard (Thesis advisor)

Aachen / Publikationsserver der RWTH Aachen University (2013) [Doktorarbeit]

Seite(n): VIII, 104 S., graph. Darst.

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.

Identifikationsnummern

  • URN: urn:nbn:de:hbz:82-opus-47403
  • REPORT NUMBER: RWTH-CONV-144013