דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
איליה אברבוך (הרצאה סמינריונית לדוקטורט)
event date icon
יום רביעי, 20.10.2010, 14:00
event location icon
Taub 601
event speaker icon
מנחה: Prof. J. A. Makowsky
Graph polynomials are powerful and well-developed tools to express graph parameters. Usually graph polynomials are compared to each other by ad-hoc means allowing to decide whether a newly defined graph polynomial generalizes (or is generalized) by another one. We study their distinctive power and introduce the notions of $dp$-completeness and universality of graph polynomials in order to formalize dependencies between them. Many known graph polynomials satisfy linear recurrence relations with respect to some set of edge- or vertex-elimination operations. Inspired by the work of Brylawski and Oxley on the Tutte polynomial, we define several classes of graph polynomials according to their recurrence relations, and prove $dp$-completeness and universality results for those classes. The talk is self-contained and does not require any prior knowledge on graph polynomials.