GYO algorithm: Difference between revisions

Revision as of 00:41, 4 February 2024

Revision as of 00:45, 4 February 2024

Line 1:

{{One source|date=December 2023}}

The '''GYO algorithm'''<ref name="yu79">{{Cite web |title=An algorithm for tree-query membership of a distributed query {{!}} IEEE Conference Publication {{!}} IEEE Xplore |url=https://ieeexplore.ieeedoi.org/document10.1109/762509 |access-date=2023-12-12 |website=ieeexploreCMPSAC.ieee1979.org}}762509</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

The algorithm was proposed in 1979 by [[Martin H. Graham|Graham]] and independently by Yu and [[Meral Özsoyoglu|Özsoyoğlu]], hence its name.

Line 30:

{{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>{{Citationcite arxiv|last=Brault-Baron |first=Johann |title=Hypergraph Acyclicity Revisited |date=2014-03-27 |arxiv=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}}

== Running time ==