{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:50436"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:50436","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Edge search in graphs using incidence tests","abstract":"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.","abstract_html":"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 <span class=\"etd-inline-math\">c<sub>p</sub>(2,n)</span> 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 &quot;Is at least one of the vertices of $X$ an endpoint of $e$?&quot;, where $X$ is a subset of $V$ with cardinality at most $p$. What is then the minimum number <span class=\"etd-inline-math\">c<sub>p</sub>(G)</span> 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 <span class=\"etd-inline-math\">c<sub>p</sub>(G)</span>. We show furthermore that the computation of <span class=\"etd-inline-math\">c<sub>p</sub>(G)</span> 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 <span class=\"etd-inline-math\">c<sub>2</sub></span> 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 <span class=\"etd-inline-math\">c<sub>2</sub>(G)</span>. We characterize the graphs for which this bound is exact in several ways. As a conclusion we receive sharp lower bounds for <span class=\"etd-inline-math\">c<sub>2</sub>(G)</span>. We also determine the 2-complexity of the complete graph and provide thus a sharp upper bound for <span class=\"etd-inline-math\">c<sub>2</sub>(G)</span> of an arbitrary graph $G$, partly characterizing the extreme case.","abstract_has_math":true,"creators":["Gerzen, Tatjana"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Triesch, Eberhard"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-30T19:40:25Z","subjects":["info:eu-repo/classification/ddc/510","Sequentielle Suche","Graph","Gruppentesten","Mathematik","Inzideztest","Gruppentetsproblem","Kantensuche","inzidenztest","grouptesting","combinatorial search","edge search"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112982%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112982%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112982%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/50436","outbound_label":"Repository record","outbound_source":"dc:identifier"},"source_record":{"url":"https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A50436","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Triesch, Eberhard"]},{"key":"dc:creator","label":"Author","values":["Gerzen, Tatjana"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2008"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-26033"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/510","Sequentielle Suche","Graph","Gruppentesten","Mathematik","Inzideztest","Gruppentetsproblem","Kantensuche","inzidenztest","grouptesting","combinatorial search","edge search"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/50436","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112982%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University 68 S. : graph. Darst. (2008). = Aachen, Techn. Hochsch., Diss., 2008"]},{"key":"dc:title","label":"Title","values":["Edge search in graphs using incidence tests"]}]}],"canonical_facts":{"dc:contributor":["Triesch, Eberhard"],"dc:coverage":["DE"],"dc:creator":["Gerzen, Tatjana"],"dc:date":["2008"],"dc:description":["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."],"dc:identifier":["https://publications.rwth-aachen.de/record/50436","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112982%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-26033"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University 68 S. : graph. Darst. (2008). = Aachen, Techn. Hochsch., Diss., 2008"],"dc:subject":["info:eu-repo/classification/ddc/510","Sequentielle Suche","Graph","Gruppentesten","Mathematik","Inzideztest","Gruppentetsproblem","Kantensuche","inzidenztest","grouptesting","combinatorial search","edge search"],"dc:title":["Edge search in graphs using incidence tests"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:40:25Z"}