About: GYO algorithm

An Entity of Type: Algorithm, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Algorithm for hypergraph acyclicity

Property Value
dbo:description
  • algorithm for hypergraph acyclicity (en)
dbp:proof
  • Assume first the GYO algorithm ends on the empty hypergraph, let be the sequence of ears that it has found, and let the sequence of hypergraphs obtained . It is clear that , the empty hypergraph, is -acyclic. One can then check that, if is -acyclic then is also -acyclic. This implies that is indeed -acyclic. For the other direction, assuming that is -acyclic, one can show that has an ear . Since removing this ear yields an hypergraph that is still acyclic, we can continue this process until the hypergraph becomes empty. (en)
dbp:title
  • The GYO algorithm ends on the empty hypergraph if and only if H is -acyclic (en)
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:label
  • GYO algorithm (en)
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International