Known properties of "canonical connections" from database theory and of "closed sets" from statistics implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls. (C) 2009 Elsevier B.V. All rights reserved.

Canonical and monophonic convexities in hypergraphs / Malvestuto, Francesco Mario. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 309:13(2009), pp. 4287-4298. [10.1016/j.disc.2009.01.003]

Canonical and monophonic convexities in hypergraphs

MALVESTUTO, Francesco Mario
2009

Abstract

Known properties of "canonical connections" from database theory and of "closed sets" from statistics implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls. (C) 2009 Elsevier B.V. All rights reserved.
2009
acyclic hypergraph; canonical connection; finite convexity space; minkowski-krein-milman property; monophonic convexity
01 Pubblicazione su rivista::01a Articolo in rivista
Canonical and monophonic convexities in hypergraphs / Malvestuto, Francesco Mario. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 309:13(2009), pp. 4287-4298. [10.1016/j.disc.2009.01.003]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/48519
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 9
social impact