18 citations · 65 across the 16 of their papers we have counts for
24 papers
A Uniform Framework for Problems on Context-Free Grammars
Javier Esparza, Peter Rossmanith, Stefan Schwoon
In a paper published in Information Processing Letters in 2000, Bouajjani et al. presented an automata-based approach to a number of elementary problems on context-free grammars. T…
Delaying Decisions and Reservation Costs
Elisabet Burjons, Fabian Frei, Matthias Gehnen +3
We study the Feedback Vertex Set and the Vertex Cover problem in a natural variant of the classical online model that allows for delayed decisions and reservations. Both problems c…
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
Jan Dreier, Daniel Mock, Peter Rossmanith
It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth- minors have constant density.…
Approximate Evaluation of First-Order Counting Queries
Jan Dreier, Peter Rossmanith
Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. They showed that there is an efficient mo…
Online Simple Knapsack with Reservation Costs
Hans-Joachim Boeckenhauer, Elisabet Burjons, Fabian Frei +3
In the online simple knapsack problem items are presented in an iterative fashion and an algorithm has to decide for each item whether to reject or permanently include it into the…
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…