Source author record

David Cariolaro

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Group Testing with Pools of Fixed Size

In the classical combinatorial (adaptive) group testing problem, one is given two integers $d$ and $n$ , where $0\le d\le n$ , and a population of $n$ items, exactly $d$ of which are known to be defective. The question is to devise an optimal sequential algorithm that, at each step, tests a subset of the population and determines whether such subset is contaminated (i.e. contains defective items) or otherwise. The problem is solved only when the $d$ defective items are identified. The minimum number of steps that an optimal sequential algorithm takes in general (i.e. in the worst case) to solve the problem is denoted by $M(d, n)$ . The computation of $M(d, n)$ appears to be very difficult and a general formula is known only for $d = 1$ . We consider here a variant of the original problem, where the size of the subsets to be tested is restricted to be a fixed positive integer $k$ . The corresponding minimum number of tests by a sequential optimal algorithm is denoted by $M^{\lbrack k\rbrack}(d, n)$ . In this paper we start the investigation of the function $M^{\lbrack k\rbrack}(d, n)$ .

preprint2013arXiv

Excessive [l,m]-factorizations

Given two positive integers l and m, with l \le m, an [l,m]-covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l \le |L| \le m for every matching L of M. An [l,m]-covering M of G is an excessive [l,m]-factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [l,m]-factorization of G (or \infty, if G does not admit an excessive [l,m]-factorization) is a graph parameter called the excessive [l,m]-index of G and denoted by χ'[l,m](G). In this paper we study such parameter. Our main result is a general formula for the excessive [l,m]-index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ'[l,m](G) and outputs an excessive [l,m]-factorization of G, whenever the latter exists.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.