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 Computation of Generalized Gyori-Lovasz Partition |
---|---|

Speaker: | Davis Issac |

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

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1 We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Thursday, 28 June 2018 |
---|---|

Time: | 11: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, it seeks a spanning tree with no tree-edge \emph{routing} too many of the original edges.
For any general connected graph with $n$ vertices and $m$ edges, we show that its STC is at most $O(\sqrt{mn})$,which is asymptotically optimal since we also demonstrate graphs with STC at least $\Omega(\sqrt{mn})$.We present a polynomial-time algorithm which computes a spanning tree with congestion $O(\sqrt{mn}\cdot \log n)$.We also present another algorithm for computing a spanning tree with congestion $O(\sqrt{mn})$; this algorithm runs in sub-exponential time when $m = \omega(n \log^2 n)$. |

Name(s): | Davis Issac |
---|

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

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

Attachments, File(s): |

Created: | Davis Issac, 05/03/2018 05:37 PM |

Last modified: | halma/MPII/DE, 04/16/2019 12:00 AM |

- Davis Issac, 05/03/2018 05:37 PM -- Created document.