m (Scipediacontent moved page Draft Content 232160265 to Gu Wang 2010a) |
|||
| 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. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| 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] | ||
Latest revision as of 17:33, 21 January 2021
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.
Original document
The different versions of the original document can be found in:
- 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://core.ac.uk/display/24625584,
- https://www.scipedia.com/public/Gu_Wang_2010a,
- https://rd.springer.com/chapter/10.1007/978-3-540-24596-4_10,
- https://academic.microsoft.com/#/detail/1545073706
Document information
Published on 01/01/2010
Volume 2010, 2010
DOI: 10.1007/978-3-540-24596-4_10
Licence: CC BY-NC-SA license
Share this document
Keywords
claim authorship
Are you one of the authors of this document?