GYO algorithm: Difference between revisions

Revision as of 16:28, 18 January 2024

Revision as of 00:41, 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.ieee.org/abstract/document/762509 |access-date=2023-12-12 |website=ieeexplore.ieee.org}}</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>{{Citation |last=Brault-Baron |first=Johann |title=Hypergraph Acyclicity Revisited |date=2014-03-27 |urlarxiv=http://arxiv.org/abs/1403.7076 |access-date=2024-01-18 |doi=10.48550/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 ==

Line 38:

== References ==

* {{Cite book |lastlast1=Abiteboul |firstfirst1=Serge |title=Foundations of Databases: The Logical Level |last2=Hull |first2=Richard |last3=Vianu |first3=Victor |date=1994-12-02 |publisher=Pearson |isbn=978-0-201-53771-0 |___location=Reading, Mass. |language=English | url=http://webdam.inria.fr/Alice/pdfs/all.pdf}} See Algorithm 6.4.4.

== Notes ==