Content deleted Content added
create minimal page |
→Principle of the algorithm: +algorithm principle |
||
Line 13:
== Principle of the algorithm ==
The algorithm iteratively removes so-called ''ears'' of the hypergraph, until the hypergraph is fully decomposed
Formally, an ''ear'' of the hypergraph ''H'' is a hyperedge ''e'' which is "almost covered" by another hyperedge ''f'', in the sense that the vertices of ''e'' can be split into two groups:
* vertices that only occur in ''e'' (and in no other hyperedge of ''H'')
* vertices that occur in ''f''.
Equivalently, the hyperedge ''e'' is an ear if it is the only hyperedge of ''H'' there is another hyperedge ''f'' such that the vertices of ''e\f'' only occur in ''e'' and in no other hyperedge of ''H''. Particular cases of ears include isolated hyperedges (i.e., those whose intersection with all other hyperedges is empty), or hyperedges that are a subset of another hyperedge.
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 hypergraph that has no ears, then the original hypergraph was not α-acyclic.
== Running time ==
The algorithm can be made to work in linear time.
== References ==
| |||