GYO algorithm - Revision history

ISaveNewspapers: spelling

2024-10-13T07:46:54Z

spelling

← Previous revision		Revision as of 07:46, 13 October 2024
Line 26:		Line 26:
	* Find an ear ''e'' in ''H''.		* Find an ear ''e'' in ''H''.
	* Remove ''e'' and remove all vertices of ''H'' that are only in ''e''.		* 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-~~emtpy~~ hypergraph that has no ears, then the original hypergraph was not α-acyclic:		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.		{{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.

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:56:11Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:56, 12 October 2024
Line 41:		Line 41:

	[[Category:Database algorithms]]		[[Category:Database algorithms]]
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:23:25Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:23, 12 October 2024
Line 41:		Line 41:

	[[Category:Database algorithms]]		[[Category:Database algorithms]]
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]

A3nm: /* Running time */ remove running time claim. From a literature search it's unclear that the GYO algorithm presented here (or its variants also called GYO algorithm) can actually be implemented in linear time. The only reference I found to test alpha-acyclicity in linear time is Tarjan and Yannakakis, 1984, which does not follow the GYO algorithm

2024-02-22T14:03:15Z

Running time: remove running time claim. From a literature search it's unclear that the GYO algorithm presented here (or its variants also called GYO algorithm) can actually be implemented in linear time. The only reference I found to test alpha-acyclicity in linear time is Tarjan and Yannakakis, 1984, which does not follow the GYO algorithm

← Previous revision		Revision as of 14:03, 22 February 2024
Line 31:		Line 31:

	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}}		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}}

	== Running time ==

	The algorithm can be made to work in linear time.

	== References ==		== References ==

A3nm: /* Principle of the algorithm */ typo

2024-02-22T13:31:12Z

Principle of the algorithm: typo

← Previous revision		Revision as of 13:31, 22 February 2024
Line 24:		Line 24:

	The GYO algorithm then proceeds as follows:		The GYO algorithm then proceeds as follows:
	* Find an ear ''e'' in ''H''		* Find an ear ''e'' in ''H''.
	* Remove ''e'' and remove all vertices of ''H'' that are only in ''e''.		* 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-emtpy hypergraph that has no ears, then the original hypergraph was not α-acyclic:		If the algorithm successfully eliminates all vertices, then the hypergraph is α-acylic. Otherwise, if the algorithm gets to a non-emtpy hypergraph that has no ears, then the original hypergraph was not α-acyclic:

A3nm: /* Principle of the algorithm */ typo

2024-02-22T13:30:55Z

Principle of the algorithm: typo

← Previous revision		Revision as of 13:30, 22 February 2024
Line 30:		Line 30:
	{{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.		{{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}}		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}}

	== Running time ==		== Running time ==

Citation bot: Altered template type. Add: eprint, class, pages, date, title, chapter, doi, chapter-url, authors 1-2. Removed or converted URL. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2024-02-04T01:03:34Z

Altered template type. Add: eprint, class, pages, date, title, chapter, doi, chapter-url, authors 1-2. Removed or converted URL. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 01:03, 4 February 2024
Line 1:		Line 1:
	{{One source\|date=December 2023}}		{{One source\|date=December 2023}}
	The '''GYO algorithm'''<ref name="yu79">https://doi.org/10.1109/CMPSAC.1979.762509</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.		The '''GYO algorithm'''<ref name="yu79">{{cite book \| chapter-url=https://doi.org/10.1109/CMPSAC.1979.762509 \| doi=10.1109/CMPSAC.1979.762509 \| chapter=An algorithm for tree-query membership of a distributed query \| title=COMPSAC 79. Proceedings. Computer Software and the IEEE Computer Society's Third International Applications Conference, 1979 \| date=1979 \| last1=Yu \| first1=C.T. \| last2=Ozsoyoglu \| first2=M.Z. \| pages=306–312 }}</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

	The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.		The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.
Line 30:		Line 30:
	{{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.		{{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 \|~~arxiv~~=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}}		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}}

	== Running time ==		== Running time ==

Headbomb: ce

2024-02-04T00:45:14Z

← Previous revision		Revision as of 00:45, 4 February 2024
Line 1:		Line 1:
	{{One source\|date=December 2023}}		{{One source\|date=December 2023}}
	The '''GYO algorithm'''<ref name="yu79">~~{{Cite web \|title=An algorithm for tree-query membership of a distributed query {{!}} IEEE Conference Publication {{!}} IEEE Xplore \|url=~~https://~~ieeexplore.ieee~~.org/~~document~~/~~762509 \|access-date=2023-12-12 \|website=ieeexplore~~.~~ieee~~.~~org}}~~</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.		The '''GYO algorithm'''<ref name="yu79">https://doi.org/10.1109/CMPSAC.1979.762509</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

	The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.		The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.
Line 30:		Line 30:
	{{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.		{{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>{{~~Citation~~ \|last=Brault-Baron \|first=Johann \|title=Hypergraph Acyclicity Revisited \|date=2014-03-27 \|arxiv=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}}		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 \|arxiv=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}}

	== Running time ==		== Running time ==

Citation bot: Altered url. URLs might have been anonymized. Add: arxiv, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed access-date with no URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2024-02-04T00:41:20Z

Altered url. URLs might have been anonymized. Add: arxiv, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed access-date with no URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 00:41, 4 February 2024
Line 1:		Line 1:
	{{One source\|date=December 2023}}		{{One source\|date=December 2023}}
	The '''GYO algorithm'''<ref name="yu79">{{Cite web \|title=An algorithm for tree-query membership of a distributed query {{!}} IEEE Conference Publication {{!}} IEEE Xplore \|url=https://ieeexplore.ieee.org~~/abstract~~/document/762509 \|access-date=2023-12-12 \|website=ieeexplore.ieee.org}}</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.		The '''GYO algorithm'''<ref name="yu79">{{Cite web \|title=An algorithm for tree-query membership of a distributed query {{!}} IEEE Conference Publication {{!}} IEEE Xplore \|url=https://ieeexplore.ieee.org/document/762509 \|access-date=2023-12-12 \|website=ieeexplore.ieee.org}}</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

	The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.		The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.
Line 30:		Line 30:
	{{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.		{{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>{{Citation \|last=Brault-Baron \|first=Johann \|title=Hypergraph Acyclicity Revisited \|date=2014-03-27 \|~~url~~=~~http://arxiv.org/abs/~~1403.7076 ~~\|access-date=2024-01-18 \|doi=10.48550/arXiv.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}}		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>{{Citation \|last=Brault-Baron \|first=Johann \|title=Hypergraph Acyclicity Revisited \|date=2014-03-27 \|arxiv=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}}

	== Running time ==		== Running time ==
Line 38:		Line 38:
	== References ==		== References ==

	* {{Cite book \|~~last~~=Abiteboul \|~~first~~=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.		* {{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 ==		== Notes ==

MikaelMonet: Added a proof sketch that the GYO algorithm is correct

2024-01-18T16:28:19Z

Added a proof sketch that the GYO algorithm is correct

← Previous revision		Revision as of 16:28, 18 January 2024
Line 26:		Line 26:
	* Find an ear ''e'' in ''H''		* Find an ear ''e'' in ''H''
	* Remove ''e'' and remove all vertices of ''H'' that are only in ''e''.		* 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-emtpy hypergraph that has no ears, then the original hypergraph was not α-acyclic.		If the algorithm successfully eliminates all vertices, then the hypergraph is α-acylic. Otherwise, if the algorithm gets to a non-emtpy 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>{{Citation \|last=Brault-Baron \|first=Johann \|title=Hypergraph Acyclicity Revisited \|date=2014-03-27 \|url=http://arxiv.org/abs/1403.7076 \|access-date=2024-01-18 \|doi=10.48550/arXiv.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}}

	== Running time ==		== Running time ==

← Previous revision		Revision as of 01:03, 4 February 2024
Line 1:		Line 1:
	{{One source\|date=December 2023}}		{{One source\|date=December 2023}}
	The '''GYO algorithm'''<ref name="yu79">https://doi.org/10.1109/CMPSAC.1979.762509</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.		The '''GYO algorithm'''<ref name="yu79">{{cite book \| chapter-url=https://doi.org/10.1109/CMPSAC.1979.762509 \| doi=10.1109/CMPSAC.1979.762509 \| chapter=An algorithm for tree-query membership of a distributed query \| title=COMPSAC 79. Proceedings. Computer Software and the IEEE Computer Society's Third International Applications Conference, 1979 \| date=1979 \| last1=Yu \| first1=C.T. \| last2=Ozsoyoglu \| first2=M.Z. \| pages=306–312 }}</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

	The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.		The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.
Line 30:		Line 30:
	{{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.		{{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 \|~~arxiv~~=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}}		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}}

	== Running time ==		== Running time ==

← Previous revision		Revision as of 00:45, 4 February 2024
Line 1:		Line 1:
	{{One source\|date=December 2023}}		{{One source\|date=December 2023}}
	The '''GYO algorithm'''<ref name="yu79">~~{{Cite web \|title=An algorithm for tree-query membership of a distributed query {{!}} IEEE Conference Publication {{!}} IEEE Xplore \|url=~~https://~~ieeexplore.ieee~~.org/~~document~~/~~762509 \|access-date=2023-12-12 \|website=ieeexplore~~.~~ieee~~.~~org}}~~</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.		The '''GYO algorithm'''<ref name="yu79">https://doi.org/10.1109/CMPSAC.1979.762509</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph\|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

	The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.		The algorithm was proposed in 1979 by [[Martin H. Graham\|Graham]] and independently by Yu and [[Meral Özsoyoglu\|Özsoyoğlu]], hence its name.
Line 30:		Line 30:
	{{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.		{{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>{{~~Citation~~ \|last=Brault-Baron \|first=Johann \|title=Hypergraph Acyclicity Revisited \|date=2014-03-27 \|arxiv=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}}		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 \|arxiv=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}}

	== Running time ==		== Running time ==