2 citations · 4 across the 8 of their papers we have counts for
9 papers
Uniform Universal Sets, Splitters, and Bisectors
Elisabet Burjons, Peter Rossmanith
Given a subset of size of a very large universe a randomized way to find this subset could consist of deleting half of the universe and then searching the remaining part. With…
Online General Knapsack with Reservation Costs
Elisabet Burjons, Matthias Gehnen
In the online general knapsack problem, an algorithm is presented with an item of size and value and must irrevocably choose to pack such an item into the knapsac…
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…
The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs
Elisabet Burjons, Janosch Fuchs, Henri Lotze
In the area of graph drawing, the One-Sided Crossing Minimization Problem (OSCM) is defined on a bipartite graph with both vertex sets aligned parallel to each other and all edges…
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…
From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata
Elisabet Burjons, Fabian Frei, Martin Raszyk
The question whether P equals NP revolves around the discrepancy between active production and mere verification by Turing machines. In this paper, we examine the analogous problem…