2 papers
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.CG2024
On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
Afrouz Jabal Ameli, Faezeh Motiei, Morteza Saghafian
Given a finite set of red and blue points in $\Rspace^d$, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points…