Abstract
dc:descriptionThis 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).
Degree
thesis:*- Grantor dc:publisher
- Publikationsserver der RWTH Aachen University
- Year dc:date
- 2005
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sieg, Volker
- Contributors dc:contributor
-
- Triesch, Eberhard
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng
Identifiers
dc:identifier.*- OAI identifier oai:identifier
- oai:publications.rwth-aachen.de:62245