University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Guy KortsarzExport this event to calendar

Friday, March 20, 2009 — 3:30 PM to 4:30 PM EDT

Increasing connectivity of a graph from 1 to 2

Speaker: Guy Kortsarz
Affiliation: Rutgers University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Given an unweighted graph G(V,E) and a set F\subseteq V\times V the goal is to find a minimum SIZE F'\subset F such that G(V,E+F') is 2 edge-connected, namely, every edge lies in a cycle in G(V,E+F'). 

This problem is one of the most basic problems in connectivity augmentation. We have a (somewhat complex) 1.5 approximation algorithm for the problem (namely an algorithm that for every instance outputs a solution of size no more than 1.5 times the optimum solution for this instance). 
In this talk we will give some of the details of a significantly simpler 1.8 approximation for the problem. The talk is self contained.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2020 (105)
    1. November (3)
    2. October (12)
    3. September (12)
    4. August (11)
    5. July (17)
    6. June (11)
    7. May (6)
    8. March (11)
    9. February (11)
    10. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)