1 citations · 1 across the 4 of their papers we have counts for
5 papers
Dynamic Detours
Daniel Dadush, Michał Pilipczuk, Amadeus Reinald +2
Fix a parameter . We give dynamic data structures that for a fully dynamic undirected graph , updated over time by edge insertions and edge deletions, can answe…
Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk
In the Disjoint Shortest Paths problem one is given a graph and a set of vertex pairs. The question is whether there exist verte…
Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
Michał Włodarczyk
In the Disjoint Paths problem, one is given a graph with a set of vertex pairs and the task is to connect each to with a path, so that the paths are…
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs
Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk +1
Given an undirected graph and a multiset of terminal pairs , the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether has p…
Sidestepping Barriers for Dominating Set in Parameterized Complexity
Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi
We study the classic {\sc Dominating Set} problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers…