Loading Events

← Back to Events

Jakub Gajarský

Technische Universität Berlin

December 2019


Jakub Gajarský, First-order interpretations of bounded expansion classes

December 10 Tuesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of …

Find out more »
+ Export Events