Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Parameterized Complexity of Power Network Design: Coordinating Cable Placement is Hard
Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei
We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal ver…
cs.DS2024
Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
Marin Bougeret, Bart M. P. Jansen, Ignasi Sau
For a fixed graph , the -SUBGRAPH HITTING problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of as a…