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
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
  1. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)