max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | Spanning Tree Congestion and the Generalized Győri-Lovász Theorem (Part 1) |
---|---|

Speaker: | L. Sunil Chandran and Davis Issac |

coming from: | Max-Planck-Institut für Informatik - D1 |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1, D2, D3, D4, D5, RG1, SWS, MMCI We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Thursday, 9 November 2017 |
---|---|

Time: | 13:00 |

Duration: | 30 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 024 |

We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, the STC problem seeks a spanning tree such that no tree-edge routes too many of the original edges. The root of this problem dates back to at least 30 years ago, with motivations from applications in network design, parallel computing and circuit design. Variants of the problem have also seen great algorithmic applications as a preprocessing step of several important graph algorithms. |

Name(s): | Yun Kuen Cheung |
---|

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | Yun Kuen Cheung, 11/03/2017 08:53 PM | Last modified: | Uwe Brahm/MPII/DE, 11/09/2017 07:00 AM |

- Yun Kuen Cheung, 11/08/2017 06:13 PM
- Yun Kuen Cheung, 11/03/2017 08:54 PM
- Yun Kuen Cheung, 11/03/2017 08:53 PM -- Created document.