期刊论文详细信息
Journal of the Brazilian Computer Society | |
Computational aspects of the Helly property: a survey | |
Szwarcfiter, Jayme L.1  Dourado, Mitre C.1  Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil1  Protti, Fabio1  | |
关键词: Computational Complexity; Helly property; NP-complete problems.; | |
DOI : 10.1007/BF03192385 | |
学科分类:农业科学(综合) | |
来源: Springer U K | |
【 摘 要 】
In 1923, Eduard Helly published his celebrated theorem, which originated the well known Helly property. Say that a family of subsets has the Helly property when every subfamily of it, formed by pairwise intersecting subsets, contains a common element. There are many generalizations of this property which are relevant to some parts of mathematics and several applications in computer science. In this work, we survey computational aspects of the Helly property. The main focus is algorithmic. That is, we describe algorithms for solving different problems arising from the basic Helly property. We also discuss the complexity of these problems, some of them leading to NP-hardness results.【 授权许可】
Unknown
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201912010163895ZK.pdf | 518KB | download |