1 citations · 2 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
Planar Disjoint Paths, Treewidth, and Kernels
Michał Włodarczyk, Meirav Zehavi
In the Planar Disjoint Paths problem, one is given an undirected planar graph with a set of vertex pairs and the task is to find pairwise vertex-disjoint paths…
Long Directed Detours: Reduction to -Disjoint Paths
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study an "above guarantee" version of the {\sc Longest Path} problem in directed graphs: We are given a graph , two vertices and of , and a non-negative integer $k…
An LP-Rounding Approximation for Restricted Maximum Acyclic Subgraph
Fabrizio Grandoni, Tomasz Kociumaka, Michał Włodarczyk
In the classical Maximum Acyclic Subgraph problem (MAS), given a directed-edge weighted graph, we are required to find an ordering of the nodes that maximizes the total weight of f…