The GYO algorithm[1] is an algorithm that applies to hypergraphs. The algorithm takes as input a hypergraph and determines if the hypergraph is α-acyclic. If so, it computes a decomposition of the hypergraph.
The algorithm was proposed in 1979 by Graham and independently by Yu and Özsoyoğlu, hence its name.
A hypergraph is a generalization of a graph. Formally, a hypergraph
H=(V,E)
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 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.
The algorithm iteratively removes the so-called ears of the hypergraph, until the hypergraph is fully decomposed.
Formally, we say that a hyperedge e of a hypergraph
H
e
e'
e\cape'=\emptyset
e
f
e\setminusf
e
In particular, every edge that is a subset of another edge is an ear.
The GYO algorithm then proceeds as follows:
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: