5 papers
aleph_0-categorical Structures: Endomorphisms and Interpretations
Manuel Bodirsky, Markus Junker
We extend the Ahlbrandt--Ziegler analysis of interpretability in aleph_0-categorical structures by showing that existential interpretation is controlled by the monoid of self--embe…
A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning
Manuel Bodirsky, Jan Kara
We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The a…
On the logical complexity of convex polygon dissections
Manuel Bodirsky, Mihyun Kang, Oleg Verbitsky
The logical depth of a graph is the minimum quantifier depth of a first order sentence defining up to isomorphism in the language of the adjacency and the equality relation…
Enumeration and limit laws of series-parallel graphs
Manuel Bodirsky, Omer Gimenez, Mihyun Kang +1
We show that the number of labelled series-parallel graphs on vertices is asymptotically , where and are explicit computable cons…
Enumeration of Unlabeled Outerplanar Graphs
Manuel Bodirsky, Eric Fusy, Mihyun Kang +1
We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number g_n of unlabeled outerplanar graphs on n vertices can be computed in polynomial time,…