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

אירועים

Completeness and Universality Properties of Graph Invariants and Graph Polynomials
event speaker icon
איליה אברבוך, הרצאה סמינריונית לדוקטורט
event date icon
יום רביעי, 20.10.2010, 14:00
event location icon
טאוב 601
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.
[בחזרה לאינדקס האירועים]