The GYO algorithm
is an algorithm that applies to
hypergraph
In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
s. 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
Graham or Graeme may refer to:
People
* Graham (given name), an English-language given name
* Graham (surname), an English-language surname
* Graeme (surname), an English-language surname
* Graham (musician) (born 1979), Burmese singer
* Clan ...
and independently by Yu and
Özsoyoğlu, hence its name.
Definition
A
hypergraph
In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
is a generalization of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
. Formally, a hypergraph
consists of a set of
vertices ''V'', and of a set ''E'' of
hyperedge
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
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
A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
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.
Principle of the algorithm
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
is an ear if one of the following two conditions holds:
*
is ''isolated'', i.e., for every other hyperedge
, we have
;
*
is almost ''covered'' by another hyperedge, i.e., there exists another hyperedge
such that all vertices in
occur only in
.
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:
References
* {{Cite book , last1=Abiteboul , first1=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
Database algorithms
Graph algorithms