5 papers
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
Martin Grohe, Christoph Koch, Nicole Schweikardt
We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is…
Computing Crossing Numbers in Quadratic Time
Martin Grohe
We show that for every fixed non-negative integer k there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, c…
Deciding first-order properties of locally tree-decomposable structures
Markus Frick, Martin Grohe
We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable c…
Local tree-width, excluded minors, and approximation algorithms
Martin Grohe
The local tree-width of a graph G=(V,E) is the function ltw^G: N -> N that associates with every natural number r the maximal tree-width of an r-neighborhood in G. Our main graph t…
Fixed-parameter tractability, definability, and model checking
Joerg Flum, Martin Grohe
In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized m…