Canonical and monophonic convexities in hypergraphs
| Autor: | Francesco M. Malvestuto |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Convex hull
Discrete mathematics Class (set theory) Hypergraph Closed set Convexity Canonical theory Theoretical Computer Science Combinatorics Canonical connection Mathematics::Metric Geometry Discrete Mathematics and Combinatorics Set theory acyclic hypergraph canonical connection finite convexity space minkowski-krein-milman property monophonic convexity Mathematics |
| Zdroj: | Discrete Mathematics. 309(13):4287-4298 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2009.01.003 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect