Content deleted Content added
MikaelMonet (talk | contribs) m shortened the definition of an ear |
m spelling |
||
| (9 intermediate revisions by 5 users not shown) | |||
Line 1:
{{One source|date=December 2023}}
The '''GYO algorithm'''<ref name="yu79">{{
The algorithm was proposed in 1979 by [[Martin H. Graham|Graham]] and independently by Yu and [[Meral Özsoyoglu|Özsoyoğlu]], hence its name.
Line 24:
The GYO algorithm then proceeds as follows:
* Find an ear ''e'' in ''H''.
* Remove ''e'' and remove all vertices of ''H'' that are only in ''e''.
If the algorithm successfully eliminates all vertices, then the hypergraph is α-acylic. Otherwise, if the algorithm gets to a non-
{{Proof|proof=Assume first the GYO algorithm ends on the empty hypergraph, let <math>e_1,\ldots,e_m</math> be the sequence of ears that it has found, and let <math>H_0,\ldots,H_m</math> the sequence of hypergraphs obtained (in particular <math>H_0 = H</math> and <math>H_m</math> is the empty hypergraph). It is clear that <math>H_m</math>, the empty hypergraph, is <math>\alpha</math>-acyclic. One can then check that, if <math>H_n</math> is <math>\alpha</math>-acyclic then <math>H_{n-1}</math> is also <math>\alpha</math>-acyclic. This implies that <math>H_0</math> is indeed <math>\alpha</math>-acyclic.
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 ==
* {{Cite book |
== Notes ==
| |||