Campus Event Calendar
Event Entry
What and Who
On the Complexity of Evaluating Graph Polynomials
Prof. Markus Bläser
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 26 January 2006
13:00
-- Not specified --
45 - FR 6.2 (E1 3)
016
Saarbrücken
Abstract
Graph polynomials encode aspects of the combinatorial structure of a graph. The chromatic polynomial, for instance, counts the number of ways to color a graph with a given number of colors. It is a special case of the univariate Tutte polynomial which itself is a special case of the multivariate Tutte polynomial. In the first part, we look at some important
graph polynomials and its properties.
Evaluating the Tutte polynomial at some point is #P-complete for "most" points where "most"
points means for all points but the zero-set of some polynomial (i.e., for a Zariski-open set). For the Tutte polynomial, this set can be described fairly precisely. We finally describe techniques for proving similar results for other graph polynomials.
graph polynomials and its properties.
Evaluating the Tutte polynomial at some point is #P-complete for "most" points where "most"
points means for all points but the zero-set of some polynomial (i.e., for a Zariski-open set). For the Tutte polynomial, this set can be described fairly precisely. We finally describe techniques for proving similar results for other graph polynomials.
Contact
--email hidden
passcode not visible
logged in users only
Veronika Weinand, 01/23/2006 12:48
Veronika Weinand, 10/19/2005 13:11
Veronika Weinand, 10/19/2005 13:08 -- Created document.
Veronika Weinand, 10/19/2005 13:11
Veronika Weinand, 10/19/2005 13:08 -- Created document.