Content deleted Content added
m Clean up duplicate template arguments using findargdups |
m spelling |
||
| (15 intermediate revisions by 8 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 5 ⟶ 6:
== Definition ==
A [[hypergraph]] is a generalization of a [[Graph (discrete mathematics)|graph]]. Formally, a hypergraph <math>H = (V, E)</math> consists of a set of [[vertex (graph theory)|vertices]] ''V'', and of a set ''E'' of [[hyperedge]]s, each of which is a subset of the vertices ''V''. Given a hypergraph, we can define its ''primal graph'' as the undirected graph defined on the same set of vertices, in which we put an edge between any two vertices which occur together in some hyperedge.
A hypergraph ''H'' is '''α-acyclic''' if it satisfies two conditions: being chordal and being conformal. More precisely, we say that ''H'' is chordal if its primal graph is a [[chordal graph]]. We say that ''H'' is conformal if, for every [[clique (graph theory)|clique]] of the primal graph, there is a hyperedge of ''H'' containing all the vertices of the clique.
The GYO algorithm takes as input a hypergraph and determines if it is α-acyclic in this sense.
Line 13 ⟶ 14:
== Principle of the algorithm ==
The algorithm iteratively removes the so-called ''ears'' of the hypergraph, until the hypergraph is fully decomposed.
Formally,
* <math>e</math> is ''isolated'', i.e., for every other hyperedge <math>e'</math>, we have <math>e \cap e' = \emptyset</math>;
* <math>e</math> is almost ''covered'' by another hyperedge, i.e., there exists another hyperedge <math>f</math> such that all vertices in <math>e \setminus f</math> occur only in <math>e</math>.
In particular, every edge that is a subset of another edge is an ear.
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-empty 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 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 ==
<references/>
[[Category:Database algorithms]]
[[Category:Graph algorithms]]
| |||