9 citations · 14 across the 11 of their papers we have counts for
6 papers · 1 filter
Improved Weighted Matching in the Sliding Window Model
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad +1
We consider the Maximum-weight Matching (MWM) problem in the streaming sliding window model of computation. In this model, the input consists of a sequence of weighted edges on a g…
List Locally Surjective Homomorphisms in Hereditary Graph Classes
Pavel Dvořák, Monika Krawczyk, Tomáš Masařík +3
A locally surjective homomorphism from a graph to a graph is an edge-preserving mapping from to that is surjective in the neighborhood of each vertex in .…
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop +3
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensive…
Anti-Path Cover on Sparse Graph Classes
Pavel Dvořák, Dušan Knop, Tomáš Masařík
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vert…
Target Set Selection in Dense Graph Classes
Pavel Dvořák, Dušan Knop, Tomáš Toufar
In this paper, we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a…
Parameterized complexity of length-bounded cuts and multi-cuts
Dušan Knop, Pavel Dvořák
We show that the Minimal Length-Bounded L-But problem can be computed in linear time with respect to L and the tree-width of the input graph as parameters. In this problem the task…