2 citations · 2 across the 4 of their papers we have counts for
4 papers
Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
Nadym Mallek, Kirill Simonov
We study the Requirement Cut problem, a generalization of numerous classical graph partitioning problems including Multicut, Multiway Cut, -Cut, and Steiner Multicut among other…
A Parameterized Study of Secluded Structures in Directed Graphs
Jonas Schmidt, Shaily Verma, Nadym Mallek
Given an undirected graph and an integer , the Secluded -Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property and has at most $…
Optimal Padded Decomposition For Bounded Treewidth Graphs
Arnold Filtser, Tobias Friedrich, Davis Issac +4
A -padded decomposition of an edge-weighted graph is a stochastic decomposition into clusters of diameter at most such that for every vertex , th…
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich, Davis Issac, Nikhil Kumar +2
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth- graph, there exists a (fraction…