SIA Seminar: Prasad Chebolu - Monday, March 7th, 2011

When:     Monday, March 7th, 2011, 12:00 noon
Where:    DIS - Department of Computer Engineering, via Ariosto 25
Room B2 "Marco Cadoli",  ground floor
Speaker: Prasad Chebolu, Department of Computer Science, University of Liverpool

Title: Algorithms for Random Graphs and Counting

In this talk, I will give a brief overview of my research interests. I will present an algorithm for counting Euler tours in a certain class of graphs and an algorithm for identifying maximum matchings in a random graph. I will then present a simple polynomial-time algorithm to exactly count the number of Euler Tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. We will extend this result to the broader class of bounded treewidth graphs. This is the first polynomial-time algorithm to count Euler tours in any class of graphs. I would then present a linear expected time algorithm for finding a maximum cardinality matching in a sparse random graph. This is optimal and improves on previous results by a logarithmic factor.