5 results
Filters
Settings
Now showing1 - 5 of 5
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Recent advances in practical data reduction(Springer, 2023-01-18); ; ; ; Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. We survey recent trends in data reduction engineering results for selected problems. Moreover, we describe concrete techniques that may be useful for future implementations in the area and give open problems and research questions.Publicationtype: Book PartScopus© Citations 5 181 310 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Parameterized algorithms for generalizations of directed feedback vertex setPublicationtype: Journal ArticleScopus© Citations 1 149 156 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Dynamic parameterized problems and algorithms(Association for Computing Machinery (ACM), 2020); ; Publicationtype: Journal Article186 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Solving packing problems with few small items using rainbow matchingsAn important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no “small” items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items. Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4k · k! · nO(1). To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Packing with run time O((k!)2 · k · 2k · n log(n)).Publicationtype: Conference PaperScopus© Citations 2 352 211 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Hitting long directed cycles is fixed-parameter tractable(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2020); ; In the Directed Long Cycle Hitting Set problem we are given a directed graph G, and the task is to find a set S of at most k vertices/arcs such that G − S has no cycle of length longer than `. We show that the problem can be solved in time 2O(`6+`k3 log k+k5 log k log `) · nO(1), that is, it is fixed-parameter tractable (FPT) parameterized by k and `. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of Mixed Graph Feedback Vertex Set [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) Feedback Vertex Set and the Directed Feedback Vertex Set problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles of length longer than and can be seen as an exact version of the approximation algorithm following from the Erdős-Pósa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015]. © Alexander Göke, Dániel Marx, and Matthias Mnich; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).Publicationtype: Conference PaperScopus© Citations 4 299 187