Hypergraph Acyclicity Revisited
| Autor: | Johann Brault-Baron |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Hypergraph
General Computer Science Computer science Computer Science::Information Retrieval 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics 010201 computation theory & mathematics FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Mathematics - Combinatorics 020201 artificial intelligence & image processing Combinatorics (math.CO) Equivalence (formal languages) Algorithm |
| Popis: | The notion of graph acyclicity has been extended to several notions of hypergraph acyclicity. In increasing order of generality: gamma acyclicity, beta acyclicity, and alpha acyclicity have met a great interest in many fields. For each notion, we prove the equivalence between the numerous characterizations with a new, simpler proof, in a self-contained manner. For that purpose, we introduce new notions of alpha, beta, and gamma leaf that allow one to define new “rule-based” characterizations of each notion. The combined presentation of the notions is completed with a study of their respective closure properties. New closure results are established, and alpha, beta, and gamma acyclicity are proved optimal w.r.t. their closure properties. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|