GYO algorithm: Difference between revisions

Revision as of 16:28, 18 January 2024

Latest revision as of 07:46, 13 October 2024

(8 intermediate revisions by 4 users not shown)

Line 1:

{{One source|date=December 2023}}

The '''GYO algorithm'''<ref name="yu79">{{Citecite webbook |title chapter-url=https://doi.org/10.1109/CMPSAC.1979.762509 | doi=10.1109/CMPSAC.1979.762509 | chapter=An algorithm for tree-query membership of a distributed query {{!}}| title=COMPSAC 79. Proceedings. Computer Software and the IEEE Computer Society's Third International Applications Conference, Publication1979 {{!}}| IEEEdate=1979 Xplore| last1=Yu |url first1=https://ieeexploreC.ieeeT.org/abstract/document/762509 |access-date last2=2023-12-12Ozsoyoglu |website first2=ieeexploreM.ieeeZ.org | pages=306–312 }}</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 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-emtpyempty hypergraph that has no ears, then the original hypergraph was not α-acyclic:

{{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 |urlclass=http://arxivmath.org/abs/1403.7076CO |access-dateeprint=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 ==

The algorithm can be made to work in linear time.

== 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 ==