5 papers
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 Complexity of Packing Edge-Disjoint Paths
Jan Dreier, Janosch Fuchs, Tim A. Hartmann +4
We introduce and study the complexity of Path Packing. Given a graph and a list of paths, the task is to embed the paths edge-disjoint in . This generalizes the well known H…
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 …
A practical fpt algorithm for Flow Decomposition and transcript assembly
Kyle Kloster, Philipp Kuinke, Michael P. O'Brien +4
The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transc…