Showing cs.DSShow all
2 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.DS2025
Structural Parameterization of Steiner Tree Packing
Niko Hastrich, Kirill Simonov
Steiner Tree Packing (STP) is a notoriously hard problem in classical complexity theory, which is of practical relevance to VLSI circuit design. Previous research has approached th…