Content deleted Content added
m →Principle of the algorithm: typo |
→Running time: remove running time claim. From a literature search it's unclear that the GYO algorithm presented here (or its variants also called GYO algorithm) can actually be implemented in linear time. The only reference I found to test alpha-acyclicity in linear time is Tarjan and Yannakakis, 1984, which does not follow the GYO algorithm |
||
Line 31:
For the other direction, assuming that <math>H</math> is <math>\alpha</math>-acyclic, one can show that <math>H</math> has an ear <math>e</math>.<ref>{{cite arXiv|last=Brault-Baron |first=Johann |title=Hypergraph Acyclicity Revisited |date=2014-03-27 |class=math.CO |eprint=1403.7076 }} See Theorem 6 for the existence of an ear</ref> Since removing this ear yields an hypergraph that is still acyclic, we can continue this process until the hypergraph becomes empty.|title=The GYO algorithm ends on the empty hypergraph if and only if H is <math>\alpha</math>-acyclic}}
== References ==
| |||