{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:62245"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:62245","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Group tests on r-ary trees","abstract":"This thesis deals with group tests on complete and semi-complete r-ary trees. A complete r-ary tree consists of a root, some inner nodes and r^k leaves, where all leaves have the same distance k to the root. A semi-complete r-ary tree is a complete r-ary tree with additional leaves, that have distance k+1 to the root, filled in from left. In this work the number of group tests are examined that are needed in the worst-case to identify d defective leaves of a (semi-)complete r-ary tree B among the other non-defective leaves. A group test is a test of a set T of leaves of B, where T consists of all leaves of a (semi-)complete r-ary subtree of B. Such a test is positive, if there is at least one defective leaf that belongs to the set T. If there is no defective leaf in T the test is negative. In Chapter 2 the exact number of group tests in the worst is determined if d is known in advance. Otherwise a boundary for the number of tests is given (precisely: a r/(r-1)-competitive algorithm is presented). In Chapter 3 – which is the main part of this thesis – the number of group tests for all semi-complete r-ary trees is determined in case d is known in advance and a boundary is given if d is a priori unknown (again a r/(r-1)-competitive algorithm is presented).","abstract_html":"This thesis deals with group tests on complete and semi-complete r-ary trees. A complete r-ary tree consists of a root, some inner nodes and r^k leaves, where all leaves have the same distance k to the root. A semi-complete r-ary tree is a complete r-ary tree with additional leaves, that have distance k+1 to the root, filled in from left. In this work the number of group tests are examined that are needed in the worst-case to identify d defective leaves of a (semi-)complete r-ary tree B among the other non-defective leaves. A group test is a test of a set T of leaves of B, where T consists of all leaves of a (semi-)complete r-ary subtree of B. Such a test is positive, if there is at least one defective leaf that belongs to the set T. If there is no defective leaf in T the test is negative. In Chapter 2 the exact number of group tests in the worst is determined if d is known in advance. Otherwise a boundary for the number of tests is given (precisely: a r/(r-1)-competitive algorithm is presented). In Chapter 3 – which is the main part of this thesis – the number of group tests for all semi-complete r-ary trees is determined in case d is known in advance and a boundary is given if d is a priori unknown (again a r/(r-1)-competitive algorithm is presented).","abstract_has_math":false,"creators":["Sieg, Volker"],"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":2005,"date_issued":"2005","date_published":"2005","updated_at":"2026-07-30T19:43:19Z","subjects":["info:eu-repo/classification/ddc/510","Gruppentesten","Baum <Mathematik>","Mathematik","group tests","r-ary trees"],"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-123824%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123824%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123824%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/62245","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Triesch, Eberhard"]},{"key":"dc:creator","label":"Author","values":["Sieg, Volker"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2005"]},{"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-11129"]},{"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","Gruppentesten","Baum <Mathematik>","Mathematik","group tests","r-ary trees"]}]},{"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/62245","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123824%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis deals with group tests on complete and semi-complete r-ary trees. A complete r-ary tree consists of a root, some inner nodes and r^k leaves, where all leaves have the same distance k to the root. A semi-complete r-ary tree is a complete r-ary tree with additional leaves, that have distance k+1 to the root, filled in from left. In this work the number of group tests are examined that are needed in the worst-case to identify d defective leaves of a (semi-)complete r-ary tree B among the other non-defective leaves. A group test is a test of a set T of leaves of B, where T consists of all leaves of a (semi-)complete r-ary subtree of B. Such a test is positive, if there is at least one defective leaf that belongs to the set T. If there is no defective leaf in T the test is negative. In Chapter 2 the exact number of group tests in the worst is determined if d is known in advance. Otherwise a boundary for the number of tests is given (precisely: a r/(r-1)-competitive algorithm is presented). In Chapter 3 – which is the main part of this thesis – the number of group tests for all semi-complete r-ary trees is determined in case d is known in advance and a boundary is given if d is a priori unknown (again a r/(r-1)-competitive algorithm is presented)."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University V, 126 S. (2005). = Aachen, Techn. Hochsch., Diss., 2005"]},{"key":"dc:title","label":"Title","values":["Group tests on r-ary trees"]}]}],"canonical_facts":{"dc:contributor":["Triesch, Eberhard"],"dc:coverage":["DE"],"dc:creator":["Sieg, Volker"],"dc:date":["2005"],"dc:description":["This thesis deals with group tests on complete and semi-complete r-ary trees. A complete r-ary tree consists of a root, some inner nodes and r^k leaves, where all leaves have the same distance k to the root. A semi-complete r-ary tree is a complete r-ary tree with additional leaves, that have distance k+1 to the root, filled in from left. In this work the number of group tests are examined that are needed in the worst-case to identify d defective leaves of a (semi-)complete r-ary tree B among the other non-defective leaves. A group test is a test of a set T of leaves of B, where T consists of all leaves of a (semi-)complete r-ary subtree of B. Such a test is positive, if there is at least one defective leaf that belongs to the set T. If there is no defective leaf in T the test is negative. In Chapter 2 the exact number of group tests in the worst is determined if d is known in advance. Otherwise a boundary for the number of tests is given (precisely: a r/(r-1)-competitive algorithm is presented). In Chapter 3 – which is the main part of this thesis – the number of group tests for all semi-complete r-ary trees is determined in case d is known in advance and a boundary is given if d is a priori unknown (again a r/(r-1)-competitive algorithm is presented)."],"dc:identifier":["https://publications.rwth-aachen.de/record/62245","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123824%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-11129"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University V, 126 S. (2005). = Aachen, Techn. Hochsch., Diss., 2005"],"dc:subject":["info:eu-repo/classification/ddc/510","Gruppentesten","Baum <Mathematik>","Mathematik","group tests","r-ary trees"],"dc:title":["Group tests on r-ary trees"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:43:19Z"}