h1

h2

h3

h4

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

Edge search in graphs using incidence tests = Suche nach einer Kante im Graph mit Hilfe der Inzidenztests



Verantwortlichkeitsangabevorgelegt von Tatjana Gerzen

ImpressumAachen : Publikationsserver der RWTH Aachen University 2008

Umfang68 S. : graph. Darst.


Aachen, Techn. Hochsch., Diss., 2008


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2008-09-23

Online
URN: urn:nbn:de:hbz:82-opus-26033
URL: https://publications.rwth-aachen.de/record/50436/files/Gerzen_Tatjana.pdf

Einrichtungen

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

Inhaltliche Beschreibung (Schlagwörter)
Sequentielle Suche (Genormte SW) ; Graph (Genormte SW) ; Gruppentesten (Genormte SW) ; Mathematik (frei) ; Inzideztest (frei) ; Gruppentetsproblem (frei) ; Kantensuche (frei) ; inzidenztest (frei) ; grouptesting (frei) ; graph (frei) ; combinatorial search (frei) ; edge search (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Angenommen, wir suchen nach einer unbekannten Kante $e$ in einem gegebenen Graph $G(V,E)$. Um die Endknoten der Kante $e$ zu finden, waehlen wir eine Teilmenge $X$ von $V$ der Kardinalität höchstens $p$ und stellen Fragen der Form: „Ist mindestens einer der Knoten von $X$ ein Endknoten von $e$?”. Was ist dann die minimale Anzahl $c_p(G)$ von Fragen die notwendig sind, um $e$ im schlimmstmoeglichen Fall zu bestimmen? In der vorliegenden Arbeit lösen wir das Problem durch die Herleitung unterer Schranken und einer scharfen oberen Schranke für die $p$-Komplexität $c_p(G)$. Wir zeigen ausserdem, dass das Entscheidungsproblem, ob $c_p(G)leq k$ für eine gegebene natürliche Zahl $k$ gilt, NP-vollstaendig ist für jede natürliche Zahl $p$. Wir gehen speziell auf die Analyse der Greedy-Strategie ein und zeigen, dass das Entscheidungsproblem, ob die Anzahl der benötigten Fragen kleiner oder gleich $k$ ist, sogar dann NP-vollständig bleibt, wenn man diese einfache Strategie benutzt. Des weiteren nehmen wir eine probabilistische Analyse der Greedy-Schranke vor. Für den Fall, dass $G$ ein vollständiger Graph ist, ist das oben beschriebene Problem aequivalent zu dem $(2,n)$-Gruppentestproblem mit Testmengen der Kardinalitaet höchstens $p$. Wir präsentieren scharfe untere und obere Schranken für die Komplexität dieses Gruppentestproblems und zeigen, dass die maximale Differenz zwischen diesen beiden Schranken 3 beträgt. Wir gehen darüberhinaus ausführlich auf den gut erfassbaren Fall $p=2$ ein und geben $c_2(G)$ für gewisse Graphenklassen exakt an. Wir beweisen eine scharfe obere Schranke für die Anzahl der Kanten in einem Graphen in Abhängigkeit von $c_2(G)$ und leiten daraus eine scharfe untere Schranke für $c_2(G)$ ab. Die Graphen, für die Gleichheit gilt, werden auf unterschiedliche Weisen charakterisiert, und wir vermuten, dass diese Charakterisierung benutzt werden kann, um für solche Graphen einen polynomiellen Algorithmus zur Berechnung von $c_2(G)$ zu konstruieren. Außerdem leiten wir eine scharfe obere Schranke für $c_2(G)$ her und geben notwendige und hinreichende Bedingungen an Graphen für das Annehmen dieser oberen Schranke an.

In this work we consider the $(2,n)$ group testing problem with test sets of cardinality at most $p$. We present sharp upper and lower bounds for the worst case number $c_p(2,n)$ of tests for this group testing problem and show that the maximum difference between the upper and lower bounds is 3. Furthermore we consider the following generalization of the $(2, n)$ group testing problem: We interpret the search domain $V$ as the vertex set of an arbitrary, finite, simple, undirected graph $G$ with edge set $E$ and search for two defect elements from $V$, i.e an unknown edge $e$ in $E$. We search for the endpoints of $e$ by asking questions of the form "Is at least one of the vertices of $X$ an endpoint of $e$?", where $X$ is a subset of $V$ with cardinality at most $p$. What is then the minimum number $c_p(G)$ of questions, which are needed in the worst case to find $e$? We solve this search problem suggested by M. Aigner by deriving lower and sharp upper bounds for $c_p(G)$. We show furthermore that the computation of $c_p(G)$ is an NP-complete problem. We prove that the decision problem whether the worst case p-complexity of a graph is smaller than an integer $k$ is an NP-complete problem even if we use the greedy strategy. In addition, we establish some probabilistic results for the greedy bound. Moreover, we elaborate on the tractable case $p=2$. We present exact results on $c_2$ for some graph classes. By means of these results we continue with the proof of sharp upper bound for the number of edges of $G$, which depends on $c_2(G)$. We characterize the graphs for which this bound is exact in several ways. As a conclusion we receive sharp lower bounds for $c_2(G)$. We also determine the 2-complexity of the complete graph and provide thus a sharp upper bound for $c_2(G)$ of an arbitrary graph $G$, partly characterizing the extreme case.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Externe Identnummern
HBZ: HT015785619

Interne Identnummern
RWTH-CONV-112982
Datensatz-ID: 50436

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 2013-01-25, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

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