The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs

Autor: Burjons, Elisabet, Fuchs, Janosch, Lotze, Henri

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 being drawn as straight lines. The task is to find a permutation of on

Externí odkaz: http://arxiv.org/abs/2201.04061

From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata

Autor: Burjons, Elisabet, Frei, Fabian, Raszyk, Martin

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 for finite transducers and automata. Every nondeterministic finite tr

Externí odkaz: http://arxiv.org/abs/2005.13710

Reoptimization of Parameterized Problems

Autor: Böckenhauer, Hans-Joachim, Burjons, Elisabet, Raszyk, Martin, Rossmanith, Peter

Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring

Externí odkaz: http://arxiv.org/abs/1809.10578

Reoptimization of parameterized problems.

Autor: Böckenhauer, Hans-Joachim¹ (AUTHOR) hjb@inf.ethz.ch, Burjons, Elisabet² (AUTHOR) burjons@cs.rwth-aachen.de, Raszyk, Martin¹ (AUTHOR) martin.raszyk@inf.ethz.ch, Rossmanith, Peter² (AUTHOR) rossmani@cs.rwth-aachen.de

Publikováno v: Acta Informatica. Aug2022, Vol. 59 Issue 4, p427-450. 24p.

Online Simple Knapsack with Reservation Costs

Autor: Böckenhauer, Hans-Joachim, Burjons, Elisabet, Hromkovič, Juraj, Lotze, Henri, Rossmanith, Peter

Publikováno v: Wadern : Schloss Dagstuhl-Leibniz-Zentrum für Informatik [16:1]-16:18 (2021). doi:10.4230/LIPICS.STACS.2021.16
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) / Herausgeber: Markus Bläser, Benjamin Monmege
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) / Herausgeber: Markus Bläser, Benjamin Monmege38. International Symposium on Theoretical Aspects of Computer Science, STACS 2021, online, 2021-03-16-2021-03-19
arXiv
Leibniz International Proceedings in Informatics (LIPIcs), 187
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

In the Online Simple Knapsack Problem we are given a knapsack of unit size 1. Items of size smaller or equal to 1 are presented in an iterative fashion and an algorithm has to decide whether to permanently reject or include each item into the knapsac

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c752e0d14b57fe29b3cbd67fc90cebca
https://publications.rwth-aachen.de/record/816354