Tutte seminar - Joseph Cheriyan

Friday, September 17, 2010 3:30 pm - 4:30 pm EDT (GMT -04:00)

Approximation algorithms for min-cost (S,T) connectivity

Speaker: Joseph Cheriyan
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158


One of the well-known problems in network design is to find a minimum-cost strongly-connected spanning subgraph of a directed network. We study a natural generalization on directed networks called the min-cost (S,T) connectivity problem. The talk will introduce this and some related techniques.