go-v.orgdoi

Complexity Aspects of the Helly Property: Graphs and Hypergraphs

Mitre Costa Dourado, Fábio Protti, Jayme Luiz SZWARCFITER · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/38
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2009

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009

Abstract

In 1923, Eduard Helly published his celebrated theorem, which originated the well known Helly property. A family of subsets has the Helly property when every sub-family thereof, formed by pairwise intersecting subsets, contains a common element. Many generalizations of this property exist which are relevant to some fields of mathematics, and have several applications in computer science. In this work, we survey complexity aspects of the Helly property. The main focus is on characterizations of several classes of graphs and hypergraphs related to the Helly property. 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.

Open the resolved locator · 10.37236/38

Metadata licence: OpenAlex metadata (CC0)