GYO algorithm: Difference between revisions

Revision as of 00:45, 4 February 2024

Latest revision as of 07:46, 13 October 2024

(6 intermediate revisions by 3 users not shown)

Line 1:

{{One source|date=December 2023}}

The '''GYO algorithm'''<ref name="yu79">{{cite book | 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, 1979 | date=1979 | last1=Yu | first1=C.T. | last2=Ozsoyoglu | first2=M.Z. | 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>{{cite arxivarXiv|last=Brault-Baron |first=Johann |title=Hypergraph Acyclicity Revisited |date=2014-03-27 |arxivclass=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}}

== Running time ==

The algorithm can be made to work in linear time.

== References ==