Computational Aspects of the Helly Property: a Survey

Mitre C. DouradoFábio ProttiJayme L. Szwarcfiter

In 1923, Eduard Helly published his celebrated theorem,which originated the well known Helly property. Saythat a family of subsets has the Helly property when everysubfamily of it, formed by pairwise intersecting subsets,contains a common element. There are many generalizationsof this property which are relevant to some partsof mathematics and several applications in computer science.In this work, we survey computational aspects ofthe Helly property. The main focus is algorithmic. Thatis, we describe algorithms for solving different problemsarising from the basic Helly property. We also discussthe complexity of these problems, some of them leading toNP-hardness results.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: