On the Complexity of Searching in Trees: Average-case Minimization (2009)
Cicalese, Ferdinando, Jacobs, Tobias, Laber, Eduardo, Molinaro, Marco
We focus on the average-case analysis: A function w : V -> Z+ is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of...
09281 Abstracts Collection -- Search Methodologies (2009)
Ahlswede, Rudolf, Cicalese, Ferdinando, Vaccaro, Ugo
From 05.07.09 to 10.07.09, the Dagstuhl Seminar 09281 on ``Search Methodologies '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. Abstracts of the presentations given during the...
2-Stage Fault Tolerant Interval Group Testing (2008)
Abteilung Informationstechnik, Ferdinando Cicalese, José Augusto, Amgarten Quitzau, Impressum Herausgeber, ...
Abstract. We study the following fault tolerant variant of the interval group testing model: Given three positive integers n, p,e, determine the minimum number of questions needed to identify a...
Computing with priced information : game trees and the value dependent cost model (2008)
Cicalese, Ferdinando, Milanic, Martin
We study the function evaluation problem in the priced information framework introduced in [Charikar et al. 2002]. We characterize the best possible extremal competitive ratio for the class of game...
On parsimony haplotyping (2008)
Cicalese, Ferdinando, Milanic, Martin
We present some structural and algorithmic results related to the parsimony haplotyping problem.
Abteilung Informationstechnik, Ferdinando Cicalese, Peter Damaschke, Ugo Vaccaro, Impressum Herausgeber, ...
We consider the following constrained version of the classical Group Testing Problem: Given a finite set of items identified with the set of natural numbers 2, . . . , n} and an unknown distinguished...
Perfect minimally adaptive q-ary search with unreliable tests (0000)
We consider the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be erroneous. In the vast literature...
Perfect minimally adaptive q-ary search with unreliable tests
We consider the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be erroneous. In the vast literature...