Gu Wang 2010a - Revision history

Scipediacontent at 15:33, 21 January 2021

2021-01-21T15:33:38Z

Scipediacontent: Scipediacontent moved page Draft Content 232160265 to Gu Wang 2010a

2020-10-14T14:22:03Z

Scipediacontent moved page Draft Content 232160265 to Gu Wang 2010a

Scipediacontent: Created page with " == Abstract == The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum..."

2020-10-14T14:22:00Z

Created page with " == Abstract == The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum..."

New page

== Abstract ==

The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum congestion (the maximum number of paths that use any single link in the cycle) is minimized. This problem has many applications, including minimizing communication congestions in computer networks and parallel computations. The MCHEC problem is NP-hard. We give a 1.8-approximation algorithm for the problem. This improves the previous 2-approximation results. The algorithm has the optimal O(mn) time for the hypergraph with m hyperedges and n nodes.

Document type: Part of book or chapter of book

== Full document ==
<pdf>Media:Draft_Content_232160265-beopen993-8943-document.pdf</pdf>

== Original document ==

The different versions of the original document can be found in:

* [http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf]

← Older revision		Revision as of 15:33, 21 January 2021
Line 3:		Line 3:

	The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum congestion (the maximum number of paths that use any single link in the cycle) is minimized. This problem has many applications, including minimizing communication congestions in computer networks and parallel computations. The MCHEC problem is NP-hard. We give a 1.8-approximation algorithm for the problem. This improves the previous 2-approximation results. The algorithm has the optimal O(mn) time for the hypergraph with m hyperedges and n nodes.		The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum congestion (the maximum number of paths that use any single link in the cycle) is minimized. This problem has many applications, including minimizing communication congestions in computer networks and parallel computations. The MCHEC problem is NP-hard. We give a 1.8-approximation algorithm for the problem. This improves the previous 2-approximation results. The algorithm has the optimal O(mn) time for the hypergraph with m hyperedges and n nodes.
−
−	~~Document type: Part of book or chapter of book~~
−
−	~~== Full document ==~~
−	~~<pdf>Media:Draft_Content_232160265-beopen993-8943-document.pdf</pdf>~~


Line 15:		Line 10:

	* [http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf]		* [http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf http://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf]
		+
		+	* [http://link.springer.com/content/pdf/10.1007/978-3-540-24596-4_10 http://link.springer.com/content/pdf/10.1007/978-3-540-24596-4_10],
		+	: [http://dx.doi.org/10.1007/978-3-540-24596-4_10 http://dx.doi.org/10.1007/978-3-540-24596-4_10]
		+
		+	* [https://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf https://www.cs.sfu.ca/research/groups/NML/publication/gu-wang.pdf],
		+	: [https://dblp.uni-trier.de/db/conf/hipc/hipc2003.html#GuW03 https://dblp.uni-trier.de/db/conf/hipc/hipc2003.html#GuW03],
		+	: [https://link.springer.com/chapter/10.1007%2F978-3-540-24596-4_10 https://link.springer.com/chapter/10.1007%2F978-3-540-24596-4_10],
		+	: [https://core.ac.uk/display/24625584 https://core.ac.uk/display/24625584],
		+	: [https://www.scipedia.com/public/Gu_Wang_2010a https://www.scipedia.com/public/Gu_Wang_2010a],
		+	: [https://rd.springer.com/chapter/10.1007/978-3-540-24596-4_10 https://rd.springer.com/chapter/10.1007/978-3-540-24596-4_10],
		+	: [https://academic.microsoft.com/#/detail/1545073706 https://academic.microsoft.com/#/detail/1545073706]

← Older revision	Revision as of 14:22, 14 October 2020
(No difference)