Tesis doctoral de Omer Gimenez Llach
This thesis is a contribution to the study of asymptotic enumeration and the complexity of evaluating the tutte polynomial on certain families of graphs and matroids. the main result is the obtention of a complete asymptotic expression for the number of labelled planar graphs using methods of singularity analysis. as a consequence of our work we obtain the limit probability distribution of many interesting parameters of random planar graphs on n vertices, like the number of edges or the number of connected components. With respect to our contribution to the study of the computational complexity of evaluating the tutte polynomial, we focus on three particular families of structures: the class of bounded clique-width graphs (a generalization of bounded tree-width graphs) and two sub-classes of transversal matroids, multi-path matroids, which we introduce generalizing the class of lattice-path matroids, and bicircular matroids. We prove that evaluating the tutte polynomial for bicircular matroids is #p-hard in every point of the plane except for two lines and an hyperbola. The situation is the opposite for multi-path matroids, for which we show algorithms that compute the tutte polynomial in polynomial time. As for bounded clique-width graphs, we show how to compute their tutte polynomial in sub-exponential time, a strong indication that the problem is not #p-hard.
Datos académicos de la tesis doctoral «Enumerative aspects and tutte polynomial of graphs and matroids«
- Título de la tesis: Enumerative aspects and tutte polynomial of graphs and matroids
- Autor: Omer Gimenez Llach
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 14/06/2005
Dirección y tribunal
- Director de la tesis
- Marc Noy Serrano
- Tribunal
- Presidente del tribunal: josep Díaz cort
- philippe Flajolet (vocal)
- joseph Bonin (vocal)
- dominic Welsh (vocal)