2 citations · 2 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
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…
cs.DS2024★ 2 cited
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…
cs.DS2022
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…