INTERDEPARTMENTAL SEMINAR ON ALGORITHMICS

(http://www.dis.uniroma1.it/~algo/)

(http://www.dis.uniroma1.it/~algo/)

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

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

ABSTRACT:

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.