Network seminar - Friday, June 28

[Joseph Peters <peters@cs.sfu.ca>]

NETWORK MODELLING GROUP

Friday, June 28, 11:30, ASB 10820

Yong Wang will talk about

"An overview on the MCHEC (Minimum-Congestion Hypergraph Embedding in
a Cycle) problem"

There will be food after the talk.

NOTE: Are there any volunteers for future talks?

-----------------------------------------------------------------------

Abstract

The MCHEC problem is to embed the n edges in an m-vertex hypergraph as
paths in a cycle with the same number of vertices, such that congestion 
( the maximum number of paths that use any single edge in the cycle) is
minimized.

The MCHEC problem has applications in electronic design automation,
parallel computing and computer communication. For example, in the case 
of parallel computing, the vertices represent processors and the edges 
indicate sets of processors that communicate with one another. A solution
to the MCHEC problem prescribes a routing for the interprocessor 
communications that minimizes the maximum load on any link in the network.

It has been proved that the MCHEC problem is NP-complete. In my talk I
will present several known 2-approximation algorithms for solving the MCHEC 
problem. Also I will give a brief introduction for some variants of MCHEC.