412 citations · 423 across the 12 of their papers we have counts for
5 papers · 1 filter
Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad +2
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Mon…
Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
Jan Dreier
The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order…
First-Order Model-Checking in Random Graphs and Complex Networks
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algo…
The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Preferential attachment graphs are random graphs designed to mimic properties of typical real world networks. They are constructed by a random process that iteratively adds vertice…
Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application
Jan Dreier, Philipp Kuinke, Ba Le Xuan +1
We analyze some local properties of sparse Erdos-Renyi graphs, where is the edge probability. In particular we study the behavior of very short paths. For …