Seminars

Links' Seminars and Public Events Add to google calendar
2022
Fri 28th Jan
11:00 am
12:00 pm
Add event to google
Alexandre Vigny (visio)
Title:
Separator logic, expressive power and algorithmic applications
Abstract:
First-order logic (FO) can express many algorithmic problems on graphs,
but fails to express whether two vertices are connected. We define a
new logic (separator logic) by enriching FO with connectivity
predicates connk(x, y, z1, . . . , zk) that hold true in a graph if
there exists a path between x and y after deletion of z1, . . . , zk.
In this talk I will first present a study of the expressive power of
this new logic.
I will then present algorithmic results for this logic on graph classes
that exclude a topological minor.
These results were obtained in collaboration with Michał Pilipczuk,
Nicole Schirrmacher, Sebastian Siebertz, and Szymon Toruńczyk.

Fri 21st Jan
11:00 am
12:00 pm
Add event to google
Aurélien Lemay in Seminar

Permanent link to this article: https://team.inria.fr/links/seminars/