Thumbnail
Access Restriction
Subscribed

Author Brault-Baron, Johann
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Acyclicity ♦ Rule-based characterizations
Abstract The notion of graph acyclicity has been extended to several notions of hypergraph acyclicity. In increasing order of generality: $\textit{gamma}$ acyclicity, $\textit{beta}$ acyclicity, and $\textit{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.
Description Author Affiliation: Aix Marseille Université/CNRS (Brault-Baron, Johann)
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-12-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 49
Issue Number 3
Page Count 26
Starting Page 1
Ending Page 26


Open content in new tab

   Open content in new tab
Source: ACM Digital Library